AcWing 5135. 奶牛用餐——堆(优先队列)
原题链接
中等
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int s[N], t[N];
struct Bulk
{
int idx, s, t;
}q[N];
int n, k;
LL bulk_t[N];
priority_queue<LL, vector<LL>, greater<LL>> desk_t;
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
scanf("%d%d", &s[i], &t[i]);
q[i] = {i, s[i], t[i]};
}
while(k --) desk_t.push(0);
for(int i = 1; i <= n; i ++)
{
auto x = q[i];
int idx = x.idx, s = x.s, t = x.t;
if(s >= desk_t.top()) bulk_t[idx] = s + t;
else bulk_t[idx] = desk_t.top() + t;
desk_t.push(bulk_t[idx]);
desk_t.pop();
}
for(int i = 1; i <= n; i ++) printf("%lld\n", bulk_t[i]);
return 0;
}