题面
题目描述
逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠N(1 ≤N≤20000)个地点（所有地点都以1到N之间的一个数字来表示）。现在奶牛们分成K(1≤K≤50000)个小组，第i 组有Mi(1 ≤Mi≤N)头奶牛，他们希望从Si跑到Ti(1 ≤Si<Ti≤N)。
由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小里的一部分奶牛分开乘坐班车。约翰经过调查得知班车的容量是C(1≤C≤100)，请你帮助约翰计划一个尽可能满足更多奶牛愿望的方案。
输入格式：
【输入】
第一行：包括三个整数：K，N和C，彼此用空格隔开。
第二行到K+1行：在第i+1行，将会告诉你第i组奶牛的信息：Si，Ei和Mi，彼
此用空格隔开。
输出格式：
【输出】
第一行：可以坐班车的奶牛的最大头数。
输入输出样例
输入样例#1：
8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1
输出样例#1：
10
题解
这道题很明显的一道贪心题目。
首先对每一组奶牛进行排序
类似于线段覆盖之类的题目
很显然
终点越靠前的组的优先级越高
因此，排完序之后，直接贪心求解即可。
但是，，，，洛谷的数据略水。。。。
对于任意一组，当前能够放多少就放多少
而能够放的最大数量，就是它所在的区间的最小值。
而要时时维护区间最小值显然要使用O(logn)的数据结构（看一看题目数据范围）
但是。。。在洛谷上面直接使用O(n)的暴力既可以AC
数据真的水。。。
但是我还是把线段树的AC代码放在底下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 1000100
struct tree
{
int l,r;
int num;
int lazy;
}T[MAX*4];
struct Group
{
int a,b;//从a到b
int num;//数量
}G[MAX];
bool operator <(Group a,Group b)
{
if(a.b!=b.b)
return a.b<b.b;
else
return a.a<b.a;
}
int C,N,K;
void Build(int k,int l,int r)
{
T[k]=(tree){l,r,0,0};
if(l==r)
{
T[k].num=C;
return;
}
int mid=(l+r)>>1;
Build(k*2,l,mid);
Build(k*2+1,mid+1,r);
T[k].num=min(T[k*2].num,T[k*2+1].num);
}
void Down(int k)
{
if(T[k].l==T[k].r)
{
T[k].num+=T[k].lazy;
T[k].lazy=0;
return;
}
T[k].num+=T[k].lazy;
T[k*2].lazy+=T[k].lazy;
T[k*2+1].lazy+=T[k].lazy;
T[k].lazy=0;
}
void Update(int k,int L,int R,int w)
{
Down(k);
if(T[k].l==L&&T[k].r==R)
{
T[k].lazy+=w;
Down(k);
return;
}
int mid=(T[k].l+T[k].r)>>1;
if(L<=mid&&R>mid)
{
Update(k*2,L,mid,w);
Update(k*2+1,mid+1,R,w);
}
else
if(L>mid)
Update(k*2+1,L,R,w);
else
if(R<=mid)
Update(k*2,L,R,w);
Down(k*2);
Down(k*2+1);
T[k].num=min(T[k*2].num,T[k*2+1].num);
}
int Query(int k,int L,int R)
{
Down(k);
if(T[k].l==L&&T[k].r==R)
return T[k].num;
int mid=(T[k].l+T[k].r)>>1;
int re=2000000000;
if(L<=mid&&R>mid)
{
re=min(re,Query(k*2,L,mid));
re=min(re,Query(k*2+1,mid+1,R));
}
else
if(L>mid)
re=Query(k*2+1,L,R);
else
if(R<=mid)
re=Query(k*2,L,R);
Down(k*2);
Down(k*2+1);
T[k].num=min(T[k*2].num,T[k*2+1].num);
return re;
}
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
int main()
{
K=read();N=read();C=read();
for(int i=1;i<=K;++i)
G[i]=(Group){read(),read(),read()};
sort(&G[1],&G[K+1]);
Build(1,1,N);
int ans=0;
for(int i=1;i<=K;++i)
{
int Up=min(G[i].num,Query(1,G[i].a,G[i].b));
ans+=Up;
Update(1,G[i].a,G[i].b-1,-Up);
}
cout<<ans<<endl;
return 0;
}