题意:
有n个任务,每个任务有3个参数ri,di和wi,表示必须在时刻[ri,di]之内执行,工作量为wi。处理器的速度可以为任意值,任务不一定要连续执行,可以分成若干块,求最大速度的最小值。
思路:
最大值的最小值问题可以考虑用二分法来做。
这道题目怎么判断速度合法是关键,我们可以使用秒为单位来判断。计算时使用贪心法,d值小的优先处理。用一个优先队列(d值小的优先级高),时间以秒为单位从1开始一次增加,如果一个任务的r值等于了当前时间t,说明该任务可以开始执行了,那么就把它加入到队列中。每个一秒的时间内处理该段时间内可以执行的d值最小的任务。
#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
using namespace std; const int maxn = + ; int n; struct node
{
int r, d, w;
bool operator <(const node& rhs) const
{
return d>rhs.d; //右坐标越大的优先级越低
}
}a[maxn]; bool cmp(node a, node b)
{
return a.r < b.r;
} bool check(int speed)
{
priority_queue<node> q;
int t = , cnt = ;
while (cnt<n || !q.empty())
{
while (cnt < n && a[cnt].r == t) q.push(a[cnt++]);
int s = speed;
while (!q.empty() && s!=)
{
node p = q.top();
q.pop();
int temp = min(s, p.w);
s -= temp;
p.w -= temp;
if (p.w != ) q.push(p);
}
t++;
if (!q.empty() && q.top().d == t) return false;
if (q.empty() && cnt == n) return true;
}
} int main()
{
ios::sync_with_stdio(false);
//freopen("D:\\txt.txt", "r", stdin);
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = ; i < n; i++)
{
cin >> a[i].r >> a[i].d >> a[i].w;
}
sort(a, a + n, cmp);
int left = , right = ;
while (left <= right)
{
int mid = (left + right) / ;
if (check(mid)) right = mid-;
else left = mid + ;
}
cout << left << endl;
}
}