题意:
有n个任务, 每个任务要在规定的时间[l, r]内完成, 工作量为 w, 每个任务可以分开完成。
求, 使得所有任务都完成的最大速度的最小值。
思路:
最大值最小问题, 二分。
因为是要完成所有任务, 所以先按开始时间排序, 接下来二分速度。
因为任意两个任务之间的关系只有两种, 1)相交或者包含 2)相切或者相离
如果是情况 2) 那么不需要特殊处理, 按顺序处理过去即可。
如果是情况 1) 那么需要将这个时间段内的任务按照结束时间来进行处理, 结束时间小的优先完成。
然后枚举时间, 从1 开始处理过去, 看是否能处理完所有任务即可。
代码:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 10010
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 struct node
36 {
37 int l;
38 int r;
39 int t;
40 int no;
41 bool operator < (const struct node &y) const
42 {
43 return r > y.r;
44 }
45 };
46 int n, sum;
47 struct node f[MAXN];
48 int w[MAXN];
49 bool cmp(const struct node &x, const struct node &y)
50 {
51 return x.l == y.l? x.r < y.r : x.l < y.l;
52 }
53 void read()
54 {
55 sum = 0;
56 scanf("%d", &n);
57 for(int i = 0; i < n; i ++)
58 {
59 scanf("%d %d %d", &f[i].l, &f[i].r, &f[i].t);
60 sum += f[i].t;
61 f[i].no = i;
62 }
63 sort(f, f + n, cmp);
64 }
65 bool is_ok(int x)
66 {
67 priority_queue <struct node> Q;
68 for(int i = 0; i < n; i ++)
69 w[f[i].no] = f[i].t;
70 int i = 0;
71 int pos = 1;
72 while(true)
73 {
74 while(i < n && f[i].l <= pos) Q.push(f[i ++]);
75
76 int ts = x;
77 while(!Q.empty() && ts)
78 {
79 struct node temp = Q.top();
80
81 if(temp.r <= pos) return false;
82
83 w[temp.no] -= ts;
84 if(w[temp.no] > 0)
85 ts = 0;
86 else if(w[temp.no] <= 0)
87 {
88 ts = -w[temp.no];
89 Q.pop();
90 }
91 }
92
93 if(i == n && Q.empty()) return true;
94 pos ++;
95 }
96 return false;
97 }
98 int get_ans()
99 {
100 int l = 1, r = sum;
101 while(l <= r)
102 {
103 int mid = (l + r) / 2;
104 if(is_ok(mid))
105 r = mid - 1;
106 else
107 l = mid + 1;
108 }
109 return l;
110 }
111
112 int main()
113 {
114 int T;
115 scanf("%d", &T);
116 while(T --)
117 {
118 read();
119 printf("%d\n", get_ans());
120 }
121 return 0;
122 }