首页 > 代码库 > 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之死
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。