题意：有n个任务，每个任务有三个参数r、d、w表示在[r,d]时间段内必须执行的工作量为w。处理器的工作速度可以变化，问执行中最大速度的最小值。
分析：题目显然提示了要用二分。
代码：
View Code
1 #include <stdio.h> 2 #include <iostream> 3 #include <queue> 4 #include <vector> 5 #include <string.h> 6 #include <algorithm> 7 using namespace std; 8 const int MAXN = 20000 + 10; 9 #define DEBUG 10 int max(int a, int b){ 11 return a>b?a:b; 12 } 13 int min(int a, int b){ 14 return a<b?a:b; 15 } 16 struct ZZ{ 17 int l, r, w; 18 bool operator < (const ZZ&z) const{ 19 return l<z.l; 20 } 21 }; 22 ZZ zz[MAXN]; 23 struct cmp{ 24 const bool operator()(const ZZ&a, const ZZ&b){ 25 return a.r > b.r; 26 } 27 }; 28 int need[MAXN], maxend, n; 29 priority_queue<ZZ, vector<ZZ>, cmp>q; 30 bool erfen(int lim){ 31 memset(need, 0, sizeof(need)); 32 int i=0, j=0; 33 while(!q.empty()) q.pop(); 34 while(true){ 35 while(i<n && zz[i].l<=j) q.push(zz[i++]); 36 int now = lim; 37 while(now!=0 && !q.empty()){ 38 ZZ tmp = q.top(); 39 q.pop(); 40 int h = min(now, tmp.w); 41 now -= h; 42 tmp.w -= h; 43 if(tmp.w!=0) q.push(tmp); 44 } 45 j++; 46 if(!q.empty()&&q.top().r<=j) return false; 47 if(q.empty() && i==n) return true; 48 } 49 } 50 int main(){ 51 #ifndef DEBUG 52 freopen("in.txt", "r", stdin); 53 #endif 54 int T; 55 scanf("%d", &T); 56 while(T--){ 57 scanf("%d", &n); 58 maxend=0; 59 int sum=0; 60 int i, l, r; 61 for(i=0; i<n; i++){ 62 scanf("%d%d%d", &zz[i].l, &zz[i].r, &zz[i].w); 63 maxend = max(zz[i].r, maxend); 64 sum+=zz[i].w; 65 } 66 sort(zz, zz+n); 67 l=0; 68 r=sum; 69 int ans=sum; 70 while(l<=r){ 71 int mid=(l+r)>>1; 72 if(erfen(mid)){ 73 ans=mid; 74 r=mid-1; 75 }else 76 l=mid+1; 77 } 78 printf("%d\n", ans); 79 } 80 return 0; 81 }
