UVALive 4254 Processor ——（二分+优先队列处理）

　　题目是求最小化最大值，很显然是二分，但是二分以后怎么判断mid是否可行并不容易。

　　代码参考了网上一个博客的代码。巧妙之处在于一秒一秒的考虑，这样可以把处理速度mid直接转化成1秒内实际的量来解决（避免小数问题），然后贪心考虑每次处理最早结束的工作即可。注意我这里的代码t表示的是一整秒，譬如[1,2]即t=1。

　　具体见代码：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <queue>
 5 using namespace std;
 6 const int N = 10000 + 5;
 7 
 8 struct node
 9 {
10     int l,r,w;
11     bool operator < (const node & temp) const
12     {
13         return r > temp.r;
14     }
15     void read()
16     {
17         scanf("%d%d%d",&l,&r,&w);
18         r--;
19     }
20 }p[N];
21 
22 bool cmp(node a,node b) {return a.l < b.l;}
23 
24 int n;
25 bool can(int mid)
26 {
27     priority_queue<node> Q;
28     int t = 1, i = 1;
29     for(;;)
30     {
31         while(i <= n && p[i].l <= t) Q.push(p[i++]);
32         int x = mid;
33         while(x > 0 && !Q.empty())
34         {
35             node u = Q.top(); Q.pop();
36             int sub = min(x, u.w);
37             x -= sub;
38             u.w -= sub;
39             if(u.w > 0) Q.push(u);
40         }
41         t++;
42         if(!Q.empty() && Q.top().r < t) return false;
43         if(Q.empty() && i == n + 1) return true;
44     }
45     //return false;
46 }
47 
48 int main()
49 {
50     int T;
51     scanf("%d",&T);
52     while(T--)
53     {
54         scanf("%d",&n);
55         for(int i=1;i<=n;i++) p[i].read();
56         sort(p+1,p+1+n,cmp);
57         int L = 1, R = 1e9;
58         int ans = -1;
59         while(L <= R)
60         {
61             int mid = L + R >> 1;
62             if(can(mid))
63             {
64                 ans = mid;
65                 R = mid - 1;
66             }
67             else L = mid + 1;
68         }
69         printf("%d
",ans);
70     }
71     return 0;
72 }