首页 > 代码库 > BZOJ 1555 KD之死

BZOJ 1555 KD之死

贪心,按t+w排序维护不一定放到拖车上的大根堆。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define maxn 600500using namespace std;struct GC{    int w,t,flag;}p[maxn];int n,m,maxv,cnt=0,sum=0,x;priority_queue <int> q;bool cmp(GC x,GC y){    return x.w+x.t<y.w+y.t;}int main(){    scanf("%d%d%d",&n,&m,&maxv);    for (int i=1;i<=n;i++)    {        scanf("%d%d",&p[i].w,&p[i].t);        p[i].flag=0;    }    for (int i=1;i<=m;i++)    {        scanf("%d",&x);        p[x].flag=1;    }    p[n+1].w=0;p[n+1].t=maxv;p[n+1].flag=1;    sort(p+1,p+n+1,cmp);    for (int i=1;i<=n+1;i++)    {        if (p[i].flag)        {            while ((sum>p[i].t) && (q.size()))            {                sum-=q.top();                cnt--;q.pop();            }            if (!q.size() || (sum>p[i].t))            {                printf("Foolish SD!");                return 0;            }            sum+=p[i].w;cnt++;        }        else        {            if (p[i].t>=sum)            {                sum+=p[i].w;cnt++;                q.push(p[i].w);            }            else            {                if (q.size() && p[i].t>=sum-q.top() && q.top()>p[i].w)                {                    sum-=q.top();sum+=p[i].w;                    q.pop();q.push(p[i].w);                }            }        }    }    printf("%d\n",cnt-1);    return 0;}

 

BZOJ 1555 KD之死