题意
有n个任务，每个任务有三个参数ri,di和wi，表示必须在时刻[ri,di]之内执行，工作量为wi。处理器执行速度可以变化，当执行速度为s时，工作量为wi。处理器的速度可以变化，当执行速度为s时，一个工作量为wi的任务需要执行wi/s个单位时间。任务不一定连续执行，可以分成若干块。求出处理器执行过程中最大速度的最小值。
分析
求最大值的最小值，一定要想到二分。这题的难点在于如何判断某个速度是否合法。想想电脑进程的执行过程，是分时间片进行的，那么，我们可以一秒一秒的计算，每个时刻贪心选择结束时间最早的。由于是每个时刻都进行计算，那么此时的速度就变成了一秒内的工作量，就能够直接减，避免了浮点数的运算。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #include<cstring> #include <queue> #include <vector> #include<bitset> #include<map> #include<deque> using namespace std; typedef long long LL; const int maxn = 1e5+5; const int mod = 77200211+233; typedef pair<int,int> pii; #define X first #define Y second #define pb push_back //#define mp make_pair #define ms(a,b) memset(a,b,sizeof(a)) const int inf = 0x3f3f3f3f; #define lson l,m,2*rt #define rson m+1,r,2*rt+1 typedef long long ll; #define N 1000010 struct node{ int l,r,w; bool operator <(const node &rhs)const{ return r>rhs.r; } }p[maxn]; int cmp(node a,node b){ return a.l<b.l; } int n,maxR,maxL; bool check(int s){ priority_queue<node> que; int tot=0; for(int i=maxL+1;i<=maxR;i++){ int temp = s; while(tot<n&&p[tot].l<i) que.push(p[tot++]); while(!que.empty()&&temp){ node now = que.top(); que.pop(); if(now.r<i) return false; if(temp>=now.w){ temp-=now.w; }else{ now.w-=temp; que.push(now); temp=0; } } } return que.empty(); } int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); #endif // LOCAL int t; scanf("%d",&t); while(t--){ scanf("%d",&n); maxR=0; maxL=inf; int sum=0; for(int i=0;i<n;i++){ scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].w); maxR=max(maxR,p[i].r); maxL=min(maxL,p[i].l); sum+=p[i].w; } sort(p,p+n,cmp); int l=0,r=sum,m; int ans=inf; while(l<=r){ m=(l+r)>>1; if(check(m)){ r=m-1; ans = min(ans,m); }else l=m+1; } printf("%d ",ans); } return 0; }