uva 1422-Processor(二分+優先キュー)

タイトルリンク:uva 1422-Processor
これらの問題が開始できる時間と完成しなければならない時間、および任務の仕事量を与える機械があり、機械が少なくとも毎秒どれだけの仕事量でこれらの任務を完成しなければならないかを聞く.
问题解决の考え方:2分答え、答えの上限はMaxWork*MaxN(すべて1秒以内に完成する)です.それからcでの仕事量が小さいとタスクが完成できるかどうかを判断します.1つの问题を処理する时间が连続しなくてもいいので、问题解决に难易度を上げました.
タスクを開始時間に従って小さいものから大きいものに並べ替え、時間区間を列挙します.開始時間が現在の列挙時間より小さい場合はエンキューします.
キューは優先キューで、終了時間の小さい優先満足度です.
キュー内の最初の要素の終了時間が現在の列挙時間の開始値より小さい場合、falseは、この問題を解決するためにタイムスライスが使用されないため、返されます.

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 10005;

struct state {
	int x, y, w, d;
	state() { d = 0; }
	friend bool operator < (state a, state b) {
		return a.y > b.y;
	}
}s[N];
int n, l, r;

bool cmp(const state& a, const state& b) {
	return a.x < b.x;
}

void init() {
	l = 0; r = 10000000;

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d%d%d", &s[i].x, &s[i].y, &s[i].w);
	sort(s, s + n, cmp);
}

bool judge(int c) {
	priority_queue<state> q;
	int cnt = 0, t = 0;
	state k;

	for (int i = 1; i <= 20000; i++) {
		if ( !q.empty()) {
			k = q.top();
			if (k.y + 1 <= i) return false;
		}

		while (t < n) {
			if (s[t].x < i) {
				q.push(s[t]);
				t++;
			} else break;
		}

		int cur = c;
		while (cur && !q.empty()) {
			k = q.top(); q.pop();
			int now = min(cur, k.w - k.d);
			k.d += now; cur -= now;

			if (k.w - k.d) {
				q.push(k);
			} else {
				cnt++;
			}
		}

		if (cnt == n) return true;
	}
	return false;
}

int solve() {
	while (true) {
		if (r - l == 1) break;

		int mid = (l + r) / 2;

		if (judge(mid)) r = mid;
		else l = mid;
	}
	return r;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		printf("%d
", solve());
	}
	return 0;
}