【洛谷1607】【USACO09FEB】庙会班车

题面

题目描述

逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛集市，约翰准备让奶牛们在集市上以车代步。但是，约翰木有钱，他租来的班车只能在集市上沿直线跑一次，而且只能停靠N(1 ≤N≤20000)个地点（所有地点都以1到N之间的一个数字来表示）。现在奶牛们分成K(1≤K≤50000)个小组，第i 组有Mi(1 ≤Mi≤N)头奶牛，他们希望从Si跑到Ti(1 ≤Si

输入格式：

【输入】

第一行：包括三个整数：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; }