题解 P1607 【[USACO09FEB]庙会班车Fair Shuttle】

MorsLin

2018-11-08 15:14:43

Solution

据说$NOIp$前发题解可以$\mathfrak{RP}$++ --- 因为要尽可能满足更多奶牛,所以按照这种区间贪心题的套路,先按右端点排序,然后依次遍历,能坐车的就让它们坐车,这样一定是最优的。 在贪心的时候,我们要知道在车在当前的时间段中最少有多少空位,可以用线段树维护(也可以不用线段树,但个人感觉用线段树比较好理解)。 ```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ls p<<1 #define rs p<<1|1 #define mid ((l+r)>>1) using namespace std; int read(){ int k=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') k=k*10+c-48,c=getchar(); return k; } struct zzz{ int st,en,num; }cow[50010]; bool cmp(zzz x,zzz y){ //按右端点排序 return x.en < y.en; } int tree[20010<<2],tag[20010<<2]; //以下为线段树维护区间最大值 inline void down(int l,int r,int p){ tree[ls]+=tag[p]; tree[rs]+=tag[p]; tag[ls]+=tag[p]; tag[rs]+=tag[p]; tag[p]=0; } inline void up(int p){ tree[p]=max(tree[ls],tree[rs]); } void update(int l,int r,int p,int nl,int nr,int k){ if(l>=nl&&r<=nr){ tree[p]+=k; tag[p]+=k; return ; } down(l,r,p); if(nl<=mid) update(l,mid,ls,nl,nr,k); if(nr>mid) update(mid+1,r,rs,nl,nr,k); up(p); } int query(int l,int r,int p,int nl,int nr){ int ans=0; if(l>=nl&&r<=nr) return tree[p]; down(l,r,p); if(nl<=mid) ans=max(ans,query(l,mid,ls,nl,nr)); if(nr>mid) ans=max(ans,query(mid+1,r,rs,nl,nr)); return ans; } int main(){ int k=read(),n=read(),c=read(); for(int i=1;i<=k;i++) cow[i].st=read(),cow[i].en=read()-1,cow[i].num=read(); sort(cow+1,cow+k+1,cmp); int maxn=0; for(int i=1;i<=k;i++){ //遍历区间 int x=query(1,n,1,cow[i].st,cow[i].en); if(x<c){ int f=min(c-x,cow[i].num); //当前能有几头奶牛上车 maxn+=f; update(1,n,1,cow[i].st,cow[i].en,f); } } cout<<maxn; return 0; } ```