学步园

An ``early adopter" Mr. Kim bought one of the latest notebooks which has a speed-controlled processor. The processor is able to operate at variable speed. But the higher the speed, the higher the
power consumption is. So, to execute a set of programs, adjusting the speed of the processor dynamically results in energy-efficient schedules. We are concerned in a schedule to minimize the maximum speed of the processor.

The processor shall execute a set of programs and each program P_i is given having a starting time r_i , a deadline d_i ,
and work w_i . When the processor executes the programs, for each program P_i , the work w_i should be done on the processor
within the interval [r_i, d_i] to complete P_i . Also, the processor does not have to execute a program in a contiguous interval, that is, it can interrupt
the currently running program and later resume it at the interrupted point. It is assumed that r_i , d_i , and w_i are given
positive integers. Recall that the processor can execute the programs at variable speed. If the processor runs the program P_i with work w_i at a constant speed s ,then
it takes  time to complete P_i . We also assume
that the available speeds are positive integers, that is, the processor operates only at integer points of speed. The speed is unbounded and the processor may operate at sufficiently large speeds to complete all the programs. The processor should complete
all the given programs and the goal is to find a schedule minimizing the maximum of the speeds at which the processor operates.

For example, there are five programs P_i with the interval [r_i, d_i] and work w_i , i =
1,..., 5 , where [r₁, d₁] = [1, 4] , [r₂, d₂] = [3, 6] , [r₃,d₃]
= [4, 5] , [r₄, d₄] = [4, 7] , [r₅, d₅] = [5, 8] and w₁ = 2 , w₂ =
3 , w₃ = 2 , w₄ = 2 , w₅ = 1 . Then the Figure 1 represents a schedule which minimizes the maximum speed at which
the processor operates. The maximum speed is 2 in this example.

=6in

Input 

Your program is to read from standard input. The input consists of T test cases. The number of test cases T (1T20) is
given on the first line of the input. The first line of each test case contains an integer n (1n10,
000) , the number of given programs which the processor shall execute. In the next n lines of each test case, the i -th line contain three integer numbers r_i , d_i ,
and w_i , representing the starting time, the deadline, and the work of the program P_i , respectively, where 1r_i < d_i20,
000 , 1w_i1,
000 .

Output 

Your program is to write to standard output. Print exactly one line for each test case. The line contains the maximum speed of a schedule minimizing the maximum speed at which the processor operates to
complete all the given programs.

Sample Input 

3 
5 
1 4 2 
3 6 3 
4 5 2 
4 7 2 
5 8 1 
6 
1 7 25 
4 8 10 
7 10 5 
8 11 5 
10 13 10 
11 13 5 
8 
15 18 10 
20 24 16 
8 15 33 
11 14 14 
1 6 16 
16 19 12 
3 5 12 
22 25 10

Sample Output 

2 
5 
7

题意：给定n个任务，每个任务必须在时间【R,D]内完成，每个任务工作量为W，问最小完成速率使得所有工作完成。

思路:二分答案，然后进行judge，判断的时候利用优先队列，由于时间只有20000，去枚举每个单位时间，看要给分配个那个任务，这步利用优先队列，按d越小越先出队，因为d越小肯定要越快完成越好。

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 10005;

int t, n;
struct Work {
    double r, d, w;
    friend bool operator < (Work a, Work b) {
	return a.d > b.d;
    }
} work[N]; 

bool cmp(Work a, Work b) {
    return a.r < b.r;
}

void init() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
	scanf("%lf%lf%lf", &work[i].r, &work[i].d, &work[i].w);
    sort(work, work + n, cmp);
}

bool judge(int mid) {
    priority_queue<Work>Q;
    int wn = 0;
    for (int i = 1; i <= 20000; i ++) {
	int sum = mid;
	while (work[wn].r < i && wn != n) Q.push(work[wn++]);
	while (sum != 0 && !Q.empty()) {
	    Work save = Q.top(); Q.pop();
	    if (i > save.d) return false;
	    if (save.w > sum) {
		save.w -= sum;
		sum = 0;
		Q.push(save);
	    }
	    else {
		sum -= save.w;
	    }
	}
	if (wn == n && Q.empty()) break;
    }
    if (wn == n && Q.empty())
	return true;
    return false;
}

int solve() {
    int l = 0, r = 10000000, mid;
    while (l < r) {
	if (r - l == 1) break;
	mid = (l + r)>>1;
	if (!judge(mid)) l = mid;
	else r = mid;
    }
    return r;
}

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