Uva(1422)(Processor)

链接：https://vjudge.net/problem/UVA-1422
思路：一开始以为是一道很普通的二分，后面发现没那么简单，因为区间可以重叠，所以要决策每个区间到底要完成哪个任务，然后开始枚举任务，结果反而不能得出正确的结论（如果每两个任务都要比较的话复杂度也会很高），最后看了题解，发现可以枚举时间，一共最多20000分钟，枚举时间即可，将任务按照起始时间进行排序，然后当时间大于等于任务的起始时间时就可以放入完成队列中，然后这一分钟完成的任务应该选择结束时间最早的来完成，如果还有剩余时间则继续完成下一个，否则就减去该分钟的完成量再入队即可，注意如果队首任务的完成时间大于当前枚举时间则返回false，因为这样贪心下来就确定不可能以速度d完成，二分枚举速度d即可（要学会二分+优先队列这种操作啊！！！！！！）
代码：

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

int t,n;

struct work{
    int s,e,w;
    bool operator<(const work &p)const{
        return e>p.e;
    }
}a[10001];

bool cmp(const work &a1,const work &a2){
    return a1.s<a2.s||(a1.s==a2.s&&a1.e<a2.e);
}

bool c(int d){
    priority_queue<work> qq;
    work now;
    int i=0;
for(int j=1;j<=20000;j++){
if(!qq.empty()){
    now = qq.top();
    if(now.e<j)return  false;//如果队首完成时间小于当前枚举时间，返回false
}
while(i<n&&a[i].s+1<=j){//如果下一个任务开始时间小于当前枚举时间，则入队
    qq.push(a[i++]);
}
int sum = d;
while(sum&&!qq.empty()){
    now = qq.top();
    qq.pop();
//选择任务并在这一分钟完成
    if(sum<now.w){
        now.w-=sum;
        sum = 0;
        qq.push(now);//若还有剩余则再入队即可
    }
    else sum-=now.w;
    if(i==n&&qq.empty())return true;
}
}
return false;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;++i){
            scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].w);
        }
        sort(a,a+n,cmp);
int lb = 1;
int ub = 1e7;
//二分枚举即可
while(ub>lb){
    int mid = (ub+lb)/2;
    if(c(mid))ub = mid;
    else lb = mid+1;
}
printf("%d\n",ub);
    }
    return 0;
}