AcWing 3492. 负载均衡
原题链接
中等
作者:
狂扁小子
,
2024-03-31 16:38:38
,
所有人可见
,
阅读 7
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 200010;
int v[N];
int n, m;
struct Task
{
int s, f, d; //开始,结束时间,算力消耗
};
vector<Task> task[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);//输入每台PC的算力
while (m --)
{
int a, b, c, d; //开始时间,指定PC,持续时间,算力消耗
scanf("%d%d%d%d", &a, &b, &c, &d);
int v_now = v[b]; //计算PC_b的当前算力
for (auto x : task[b])
{
if (a <= x.f) v_now -= x.d; //当这个任务的开始时间在已有任务的持续时间以内时,
//需要减去当前持续任务消耗的算力
if (v_now <= 0) break;
}
if (v_now >= d)
{
printf("%d\n", v_now - d);
task[b].push_back({a, a+c-1, d});
}
else printf("%d\n", -1);
}
return 0;
}