题目地址：http://vjudge.net/problem/UVALive-4254
计算机的速度可以是任何值，题目求的是最大速度的最小值
那么很明显就是二分查找最优解
题目就转化为：给定一个是计算机速度，求该速度下能否达成目标
最暴力的方法就是，[i,j]之间的线段都试一下，但n^2log2(n)肯定超时
那么就肯定是贪心，贪心的思路就是：你在t时刻，还有k个任务没完成，肯定会选马上要交的作业写对吧，
贪心就是这个思路，在所有任务中，选择终止时刻最小的那个，这就要用到优先队列优化了，时间是从头开始枚举的
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
struct Node
{int r,d,w;bool operator < (const Node& n) const {return d>n.d;}
}P[10000+5];
bool cmp(const Node& n1,const Node& n2){return n1.r<n2.r;
}
int n;
bool Check(int speed){priority_queue<Node> PQ;int nowTime=P[1].r*speed,pos=1;for(;;){while(pos<=n&&P[pos].r*speed<=nowTime) PQ.push(P[pos++]);int nextTaskTime=pos>n?(1<<30):P[pos].r*speed;Node task=PQ.top(); PQ.pop();int deadLine=task.d*speed;int time=nowTime+task.w;if(time>deadLine) return false;if(time>nextTaskTime) time=nextTaskTime,task.w-=time-nowTime,PQ.push(task);nowTime=time;if(PQ.empty()) {if(pos==n+1) return true;else nowTime=nextTaskTime;}}
}
int main(int argc, char const *argv[])
{int T; scanf("%d",&T);while(T--){scanf("%d",&n);REP(i,1,n) {int r,d,w; scanf("%d%d%d",&r,&d,&w);P[i]=Node{r,d,w};}sort(P+1,P+1+n,cmp);int L=1,R=1000+5; //R不能太大 ，万一溢出了while(L<=R){int mid=(L+R)>>1;if(R!=mid&&Check(mid)) R=mid;else L=mid+1;}printf("%d\n", R);}return 0;
}