UVa 1422 - Processor
传送门
题意
有N个任务，每个任务只能在开始时间到结束时间之内完成，有任务量。完成所需时间是w / 处理器速度。
输出处理器速度最大值的最小值。
思路
虽然一看就知道是二分，但是怎么Check想了一整天都没想出来。看了别人的题解。
思路是一秒一秒来算。
建一个优先队列，结束时间越短越优先，因为要最快完成。
一秒内能处理的任务量就是处理器的速度mid。
出队，如果能处理完就减掉，不能处理完就减一下任务量，因为任务还木有完成，所以还得入队。
一直重复，直到全部都出队。
代码
#include <cstdio>
#include <queue>
#include <algorithm>
#define LL long long
#define lowbit(x) ((x) & (-x))
const int MAXN = 1e4 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
struct POINT
{
int st, ed, w;
bool operator < (const POINT &a) const
{
return ed > a.ed;
}
}pit[MAXN];
int n, vmax;
priority_queue<POINT> qu;
int cmp(const POINT &a, const POINT &b)
{
return a.st < b.st;
}
bool Check(int mid)
{
while (!qu.empty()) qu.pop();
int i, j;
int k = 0;
for (i = 1; i <= 20000; i++)
{
while (pit[k].st < i && k != n) qu.push(pit[k++]);
int curLev = mid;
while (!qu.empty() && curLev != 0)
{
POINT cur = qu.top(); qu.pop();
if (cur.ed < i) return false; //取出了过时未完成的任务。
if (cur.w > curLev)
{
cur.w -= curLev;
curLev = 0;
qu.push(cur);
}
else
curLev -= cur.w;
}
}
if (qu.empty() && k == n)
return true;
return false;
}
int Solve()
{
sort(pit, pit + n, cmp);
int l = 0, r = vmax, ans, mid;
while (l <= r)
{
mid = l + (r - l) / 2;
if (Check(mid))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
return ans;
}
int main()
{
//freopen("input.txt", "r", stdin);
int T, i, j;
scanf("%d", &T);
while (T--)
{
vmax = 0;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d%d%d", &pit[i].st, &pit[i].ed, &pit[i].w);
vmax += pit[i].w;
}
printf("%d\n", Solve());
}
return 0;
}