题意：有n个任务，每一个任务必须在在时刻[r, d]之内运行w的工作量（三个变量都是整数）。处理器运行的速度能够变化，当速度为s时，一个工作量为w的任务须要 运行的时间为w/s个单位时间。
另外不一定要连续运行，能够分成若干块。
求处理器在运行过程中最大速度的最小值。
处理器速度为随意的整数值。
思路：事实上类似于最大值的最小化，也就是在满足各个任务在给定的时间区间内完毕。求速度的最小值。我们能够先将開始时间从小到大排序，之后枚举时间。開始时间比当前枚举时间小的入队伍，越早结束的任务优先处理。之后决定该单位时间处理器处理哪个任务或哪些任务。
注意推断当队列第一个元素的结束时间小于当前枚举时间，就代表这个任务没有在规定时间内完毕。所以速度不够。
#include#include #include #include #include using namespace std;const int N = 10000000;const int MAXN = 10005;struct Work{ int r, d, w; friend bool operator < (Work a, Work b) { return a.d > b.d; }}work[MAXN];int n;int cmp(Work a, Work b) { return a.r < b.r;}int judge(int mid) { priority_queue q; Work state; int cnt = 0; for (int i = 1; i <= 20000; i++) { if (!q.empty()) { state = q.top(); if (state.d < i) { return false; } } while (cnt < n && work[cnt].r + 1 <= i) { q.push(work[cnt++]); } int sum = mid; while (sum && !q.empty()) { state = q.top(); q.pop(); if (sum < state.w) { state.w -= sum; sum = 0; q.push(state); } else sum -= state.w; if (cnt == n && q.empty()) return true; } } return false;}int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d%d", &work[i].r, &work[i].d, &work[i].w); sort(work, work + n, cmp); int L = 0, R = N, mid; while (L < R) { mid = L + (R - L) / 2; if (judge(mid)) R = mid; else L = mid + 1; } printf("%d\n", L); } return 0;}