MorsLin 的博客

MorsLin 的博客

前事不忘,后事之师

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

posted on 2018-11-08 15:14:43 | under 题解 |

据说$NOIp$前发题解可以$\mathfrak{RP}$++


因为要尽可能满足更多奶牛,所以按照这种区间贪心题的套路,先按右端点排序,然后依次遍历,能坐车的就让它们坐车,这样一定是最优的。
在贪心的时候,我们要知道在车在当前的时间段中最少有多少空位,可以用线段树维护(也可以不用线段树,但个人感觉用线段树比较好理解)。

#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;
}