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（二分+贪心+优先队列）

原文：http://blog.csdn.net/keshuai19940722/article/details/18864461