BZOJ-1577: [Usaco2009 Feb]庙会捷运Fair Shuttle

Description

告诉你一辆能乘c个人的车，从1站点走到n站点。给出每个站点上车人数，以及他们的目的地。询问最多满足的人数。n<=20000，c<=100

看出来是贪心了。到一站先将车上达到目的地的人扔下去(233)，尽量上人，如果不能上人，比较目的地。如果车上人的目的地远于将要上车的人，将车上的人赶下车。

然后实现方法感觉好tm恶心啊。。。码力不行啊。

先写了个堆，然后，在删除的时候巨恶心。

然后，听某人说是线段树？？？考虑了一下，从远到近循环车上的目的地修改的话感觉also好恶心。

删除？？？插入？？？循环遍历？？？排好序？？？
想到了set。
写的时候发现一个问题，不能直接改变set的元素。说是那是read_only。那么就删了重加。
Tips:
从后向前遍历set中的元素的时候，如果操作带有删除，感觉最好每次将iterator赋值，鬼知道set删除了之后的iterator还是不是原来的iterator。
这对码力的考验。。。略微感人。

#include <set>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans,sum,c;

struct node {int tar,num;};

bool operator < (node x,node y){return x.tar==y.tar ? x.num<y.num : x.tar<y.tar;}

set <node> s;
set <node>::iterator it;

vector<node>v[21000];

int main()
{
    scanf("%d%d%d",&m,&n,&c);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back((node){y,z});
    }
    for(int i=1;i<=n;i++)
    {
        it=s.lower_bound((node){i,-1});
        if(it!=s.end()&&it->tar==i)
        {
            ans+=it->num;
            sum-=it->num;
            s.erase(it);
        }
        for(int j=0;j<v[i].size();j++)
        {
            x=v[i][j].tar,y=v[i][j].num;
            if(sum<c)
            {
                int tmp=min(c-sum,y);
                it=s.lower_bound((node){x,-1});
                if(it!=s.end()&&it->tar==x)
                {
                    int yy=it->num;
                    s.erase(it);
                    s.insert((node){x,yy+tmp});
                }
                else s.insert((node){x,tmp});
                y-=tmp; sum+=tmp;
            }
            int cc=y;
            while(y)
            {
                it=s.end();
                if(it==s.begin()) break;
                it--; if(it->tar<=x) break;
                int tmp=min(it->num,y); y-=tmp;
                int xx=it->tar,yy=it->num-tmp;
                s.erase(it);
                if(yy) s.insert((node){xx,yy});
            }
            it=s.lower_bound((node){x,-1});
            if(it!=s.end()&&it->tar==x)
            {
                int yy=it->num+cc-y;
                s.erase(it);
                s.insert((node){x,yy});
            }
            else s.insert((node){x,cc-y});
        }
    }
    printf("%d\n",ans);
    return 0;
}