本文共 2300 字，大约阅读时间需要 7 分钟。
题意：
有n个任务， 每个任务要在规定的时间[l, r]内完成， 工作量为 w， 每个任务可以分开完成。
求， 使得所有任务都完成的最大速度的最小值。
思路：
最大值最小问题， 二分。
因为是要完成所有任务， 所以先按开始时间排序， 接下来二分速度。
因为任意两个任务之间的关系只有两种， 1）相交或者包含 2）相切或者相离
如果是情况 2） 那么不需要特殊处理， 按顺序处理过去即可。
如果是情况 1） 那么需要将这个时间段内的任务按照结束时间来进行处理， 结束时间小的优先完成。
然后枚举时间， 从1 开始处理过去， 看是否能处理完所有任务即可。
代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 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"< = 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 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 }
转载于:https://www.cnblogs.com/By-ruoyu/p/4871431.html
