题意
有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+;
const int mod = +;
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=;
for(int i=maxL+;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=;
}
}
}
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=;
maxL=inf;
int sum=;
for(int i=;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=,r=sum,m;
int ans=inf;
while(l<=r){
m=(l+r)>>;
if(check(m)){
r=m-;
ans = min(ans,m);
}else l=m+;
}
printf("%d\n",ans);
}
return ;
}