CF523D 解题报告
先上结果:
前两次语言选错了,编译一直不过(
做这题是因为集训老师让我做我就做了,要不然我都快忘了我有 CF 账号了(
思路
省流:STL 大法
开一个小根堆存目前正在运行的服务器(也可以大根堆,但是存时间进去的时候存负的),如果有空机就直接处理,这个视频处理完的时间就是它进入的时间+它处理的时间;如果没有,处理时间最短的服务器处理结束的时间+它处理的时间。
需要注意的是我的代码实现时是每进来一个视频弹一个服务器,所以如果这个服务器已经处理完了它还是会在里面,这时候结束时间+视频处理时间是小于进入时间+视频处理时间的,特判一下完全 OK.
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 5 * 1e5 + 5;
ll n, k, ans[N], s, m;
priority_queue<ll, vector<ll>, greater<ll> > tim;
// ↑储存目前被占用的服务器在第几分钟时空闲
int main() {
scanf("%lld%lld", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%lld%lld", &s, &m);
ans[i] = s + m;
if(tim.empty()) tim.push(ans[i]); // 如果所有服务器都空着就直接开始处理
else {
if(tim.size() < k) tim.push(ans[i]); // 有空机
else {
ans[i] = max(tim.top() + m, ans[i]); // 特判是否有服务器已经处理完
tim.pop();
tim.push(ans[i]);
}
}
}
for(int i = 1; i <= n; ++i) printf("%lld\n", ans[i]);
// ↑输出答案
return 0;
}