<USACO09FEB>庙会捷运Fair Shuttleの思路

一个没有被我成功证明的

贪心

但是

ac了的

别人排序都是排终点.但我的排终点错了emm排起点才对qvq

有没有人友情看看怎么证(没有

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,c,k,now=,ans=,maxx=,cnt=;//now现在在车上的，maxx目前到达最远的站，cnt累计上到第几批了

int q[];//到i下车的牛数

struct node

{

    int s,e,m;

}kk[];

bool cmp(node a,node b){return a.s<b.s;}

void emm(int i)

{

    if(c>=now+kk[i].m)

    {

        q[kk[i].e]+=kk[i].m; now+=kk[i].m;

        maxx=max(maxx,kk[i].e);

        return;

    }else

    {

        int nup=now+kk[i].m-c;//这一组全上去 会多出来的

        for(int j=maxx;j>kk[i].e&&nup>;j--)//要给i波牛空位置

        {

            int end=q[j];

            q[j]=max(,q[j]-nup);//赶走一些牛//因为 它在kk[i].e以前的位置已经有第i波的那几只可以代替了，所以，它要把从kk[i].e到最后的位置给空出来 让给之后的牛

            maxx=j;

            nup-=(end-q[j]);

        }

        //若还没有牛到kk[i].e的位置.第i波能上几只上几只emm就跳过了j循环

        now=c;

        q[kk[i].e]+=kk[i].m-nup;

        maxx=max(maxx,kk[i].e);

    }

}

int main()

{

    int i,j;

    scanf("%d%d%d",&k,&n,&c);

    for(i=;i<=k;i++)scanf("%d%d%d",&kk[i].s,&kk[i].e,&kk[i].m);

    sort(kk+,kk+k+,cmp);

    cnt=;

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

    {

        if(q[i])//有牛可以下车啦

        {

            ans+=q[i];now-=q[i];

            q[i]=;

        }

        while(kk[cnt].s==i)

        {

            emm(cnt);cnt++;

        }

    }

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

return ;

}

点击查看我丑陋の代码&注释