庙会捷运 Fair Shuttle bzoj-1577 Usaco-2009 Feb

题目大意：有一辆公交车从1走到n。有m群奶牛从$S_i$到$E_i$，第i群奶牛有$W_i$只。车有一个容量c。问不走回头路的情况下最多使多少奶牛到达目的地。其中，每一群奶牛不一定都拉走。

注释：$1\le n\le 2\cdot 10^4$，$1\le m\le 5\cdot 10^4$，$1\le c\le 100$。

想法：开始觉得是个裸贪心，但是没法维护。其实是这样的：

我们将所有的奶牛群排序：右端点为第一关键字，递增；左端点为第二关键字，递减。

我们给序列上的每个数是当前公交车剩的奶牛个数。然后就是用线段树维护区间最小值，答案就加上当前奶牛群和对应区间的最小值的较小者，然后区间加。

即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 20010

#define K 50010

#define lson pos<<1

#define rson pos<<1|1

using namespace std;

int minn[N<<2],tag[N<<2]; int c;

struct Node {int l,r,w;}a[K]; inline bool cmp(const Node &x,const Node &y) {return x.r==y.r?x.l>y.l:x.r<y.r;}

inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}

int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}

inline void pushup(int pos) {minn[pos]=min(minn[lson],minn[rson]);}

inline void pushdown(int pos)

{

    if(!tag[pos]) return;

    tag[lson]+=tag[pos]; minn[lson]+=tag[pos];

    tag[rson]+=tag[pos]; minn[rson]+=tag[pos];

    tag[pos]=0;

}

void build(int l,int r,int pos)

{

    if(l==r) {minn[pos]=c; return;}

    int mid=(l+r)>>1;

    build(l,mid,lson); build(mid+1,r,rson);

    pushup(pos);

}

void update(int x,int y,int val,int l,int r,int pos)

{

    if(x<=l&&r<=y) {minn[pos]+=val; tag[pos]+=val; return;}

    int mid=(l+r)>>1; pushdown(pos);

    if(x<=mid) update(x,y,val,l,mid,lson);

    if(mid<y) update(x,y,val,mid+1,r,rson);

    pushup(pos);

}

int query(int x,int y,int l,int r,int pos)

{

    if(x<=l&&r<=y) return minn[pos];

    int mid=(l+r)>>1,ans=0x7f7f7f7f; pushdown(pos);

    if(x<=mid) ans=min(ans,query(x,y,l,mid,lson));

    if(mid<y) ans=min(ans,query(x,y,mid+1,r,rson));

    return ans;

}

int main()

{

    int n=rd(),l=rd(); c=rd(); for(int i=1;i<=n;i++)

    {

        a[i].l=rd(),a[i].r=rd(),a[i].w=rd(); a[i].r--;

    }

    int ans=0;

    sort(a+1,a+n+1,cmp); build(1,l,1);

    for(int i=1;i<=n;i++)

    {

        int temp=min(a[i].w,query(a[i].l,a[i].r,1,l,1));

        if(temp) ans+=temp,update(a[i].l,a[i].r,-temp,1,l,1);

    }

    printf("%d\n",ans);

    return 0;

}

小结：线段树是真的强啊... ...

巴特西

[bzoj1577][Usaco2009 Feb]庙会捷运Fair Shuttle_贪心_线段树

庙会捷运 Fair Shuttle bzoj-1577 Usaco-2009 Feb

最新文章

热门文章