本文共 1958 字，大约阅读时间需要 6 分钟。
题目
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2255
n个任务，允许时间区间为[ri, di](ri , di <= 20000)，运算量为wi，可以分割，问最小运算速度
思路
明显，应该二分枚举最小运算速度，
对于时刻i来说，应该优先处理已经开始的最早结束的任务。接着，如果任务已经处理完毕，那就应该等待下一个任务-也即跳到下一个r。
那么如何选择处理任务的时间点呢？可以选择每个任务开始的时候，以这个任务（和与它开始时间相同的任务）开始，而下一个任务还没有开始的时间段来处理任务。
感想：
一开始看成了di <= 1000，因此枚举速度的区间弄错了
代码
#include #include #include #include #include #include #include #include #include #include #include #define LOCAL_DEBUGusing namespace std;typedef tuple MyTask;typedef pair MyPair;const int MAXN = 1e4 + 4;MyTask tasks[MAXN];int n;bool check(int speed) { priority_queue , greater > que;//this one is Pair double nowt = 0; for (int i = 0; i < n;) { nowt = get<0>(tasks[i]); while (i < n && get<0>(tasks[i]) <= nowt) { que.push(MyPair(get<1>(tasks[i]), get<2>(tasks[i]))); i++; } double nxtt = i < n ? get<0>(tasks[i]) : 1e9; while (!que.empty() && nowt < nxtt) { int d = que.top().first; int wi = que.top().second; que.pop(); if (nowt > d)return false; if ((d - nowt) * speed < wi)return false; double addt = min((double)wi / speed, nxtt - nowt); if (addt * speed < wi) { que.push(MyPair(d, wi - addt * speed)); } nowt += addt; } } return true;}int main() {#ifdef LOCAL_DEBUG freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin); //freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);#endif // LOCAL_DEBUG int T; cin >> T; for (int ti = 1;ti <= T; ti++) { cin >> n; for (int i = 0; i < n; i++) { int ri, di, wi; cin >> ri >> di >> wi; tasks[i] = tie(ri, di, wi); } sort(tasks, tasks + n); int l = 0, r = 20000; while (l < r) { int mid = (l + r) >> 1; if (mid == l)break; if (check(mid)) { r = mid; } else { l = mid; } } cout << r << endl; } return 0;}
转载于:https://www.cnblogs.com/xuesu/p/10468051.html
