首页 > 代码库 > CodeForces 377B 优先队列 + 二分
CodeForces 377B 优先队列 + 二分
题目:
呵呵,这破题目搞了我两个小时,首先题意就有点怕怕的,n个人,具有解决bug的能力,一天只能解决一个,m个bug,bug具有一个难度,只有某个人能力大于等于这个难度才可以解决,请n个人解决一个问题,每个人都要拿钞票的,问不超过s元 的情况下 最快的解决办法
输出每个bug由哪个人解决的方案
先考虑了DP,发现不行,后来就觉得是贪心了,那么就跟优先队列联系上了,把bug的难度 跟人的 解决办法能力都从大到小排,然后开始二分枚举解决天数,假设解决天数为t,那么最厉害的那个人且花费比较合适的那个人最多使用t次,都从大到小排,然后再优先队列一下能解决问题的花费最少的人,每一次更新,若他能解决第一个问题,那么接下里的 t-1个问题他都可以解决,更新是从前往后更新的,所以肯定是最优的,中间花费超过s的方案可以舍去,没办法解决当前未解决的最大难度的bug也要舍去,二分枚举的 最后一个能成功的肯定就是最优的了,
一开始 看看是否最难的bug有人能够解决,否则 输出No
还要看看m天是否有解决方案,因为最多是使用m天,若无法解决那么输出no
接下来才枚举天数
一开始没相当去枚举解决时间,结果弄得很麻烦,后来想到了,敲了,结果中途优先队列有个地方手贱敲错了,一直在调试解决函数,真是醉了。。
int n,m,s; typedef struct Node { int id; int nnum; bool operator<(const Node &aa)const { return nnum > aa.nnum; } }; Node bug[100000 + 55]; typedef struct NODE { int id; int ablity; int cost; bool operator<(const NODE & aa)const { return cost > aa.cost; } }; NODE stu[100000 + 55]; int maxn; int ans[100000 + 55],tmp[100000 + 55]; void init() { memset(bug,0,sizeof(bug)); memset(stu,0,sizeof(stu)); } bool input() { while(cin>>n>>m>>s) { maxn = -1; for(int i=0;i<m;i++) { cin>>bug[i].nnum; bug[i].id = i + 1; maxn = max(maxn,bug[i].nnum); } for(int i=0;i<n;i++) { cin>>stu[i].ablity; stu[i].id = i + 1; } for(int i=0;i<n;i++)cin>>stu[i].cost; return false; } return true; } bool cmp(NODE x,NODE y) { return x.ablity > y.ablity; } bool isok(int t) { int ret = 0; priority_queue<NODE> q; for(int i=0,j=0;i<m;i+=t) { for(;j<n;j++) { if(stu[j].ablity >= bug[i].nnum)q.push(stu[j]); else break; } if(q.size() == 0)return false; NODE qq = q.top(); q.pop(); ret += qq.cost; if(ret > s)return false; int mark = 0; for(int j=i;j<m;j++) { tmp[bug[j].id] = qq.id; mark++; if(mark == t)break; } } for(int i=1;i<=m;i++)ans[i] = tmp[i]; return true; } void cal() { bool flag = false; for(int i=0;i<n;i++) { if(stu[i].ablity >= maxn && stu[i].cost <= s)flag = true; } if(!flag) {puts("NO");return;} sort(bug,bug + m); sort(stu,stu + n,cmp); int cc = 0; if(!isok(m)){puts("NO");return ;} int l = 1,r = m; while(l <= r) { int mid = (l + r)>>1; if(isok(mid))r = mid - 1; else l = mid + 1; } puts("YES"); for(int i=1;i<=m;i++) printf("%d%c",ans[i],i == m?'\n':' '); } void output() { } int main() { while(true) { init(); if(input())return 0; cal(); output(); } return 0; }
CodeForces 377B 优先队列 + 二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。