本文主要是介绍CodeForces 337B Preparing for the Contest（二分+贪心+优先队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：CodeForces 337B Preparing for the Contest
题目大意：有n个人，m个病毒，s张通行证，然后给出m个病毒的等级，n个人的等级，以及n个人去杀病毒所需要的通行证数量，问所最少花费几天可以杀光病毒，并输出每个病毒被那一个人所清理。PS：人要杀病毒必须等级大于等于病毒，一个人只需支付一次通行证。
解题思路：二分+贪心+优先队列。二分天数，贪心判断，每次用可以杀除当前最高等级病毒中通行证所需最少的。杀mid个大的病毒，优先队列进行优化。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>using namespace std;const int N = 100005;struct state {int id, val, pass;friend bool operator <(const state& a, const state& b) {return a.pass > b.pass;}
}p[N], bug[N];
int n, m, s;bool cmp(const state& a, const state& b) {return a.val > b.val;
}void init() {scanf("%d%d%d", &n, &m, &s);for (int i = 0; i < m; i++) {scanf("%d", &bug[i].val); bug[i].id = i;}for (int i = 0; i < n; i++) scanf("%d", &p[i].val);for (int i = 0; i < n; i++) {scanf("%d", &p[i].pass);p[i].id = i;}sort(p, p + n, cmp);sort(bug, bug + m, cmp);
}bool judge(int k) {int a = 0, b = 0, sum = s;priority_queue<state> que;while (b < m) {while (a < n) {if (p[a].val >= bug[b].val) que.push(p[a]);else break;a++;}if (que.empty()) return false;state c = que.top(); que.pop();if (sum < c.pass) return false;sum -= c.pass;b += k;}return true;
}void put(int k) {int a = 0, b = 0;int ans[N];priority_queue<state> que;while (b < m) {while (a < n) {if (p[a].val >= bug[b].val) que.push(p[a]);else break;a++;}state c = que.top(); que.pop();int t = min(m, b + k);for (int i = b; i < t; i++)ans[bug[i].id] = c.id + 1;b += k;}printf("%d", ans[0]);for (int i = 1; i < m; i++) printf(" %d", ans[i]);printf("\n");
}void solve() {if (!judge(m)) {printf("NO\n"); return;}int l = 0, r = m;while (l < r) {int mid = (l + r) / 2;if (judge(mid)) r = mid;else l = mid + 1;}printf("YES\n");put(r);
}int main() {init();solve();return 0;
}
这篇关于CodeForces 337B Preparing for the Contest（二分+贪心+优先队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
