題目大意：
給定 n 臺計算機和這 n 臺計算機的計算力，現有 m 個任務需要被分配到這 n 個計算機上，每一個任務在 a 時刻被分配到編號為 b 的計算機上，任務消耗計算機算力為d, 耗時為 c，計算機處理任務需滿足以下條件：
1.當前時刻編號 b 計算機沒有正在處理任務
2.當前時刻編號 b 計算機算力大于等于任務所需要的算力
要求輸出每處理一個任務時當前計算機剩余算力，如果計算機處理不了當前任務，該任務直接舍棄，
思路：
1.要想計算機能夠處理當前任務，首先在 a 時刻當前計算機已經處于空閑狀態，說白了就是每個任務處理的時間段（開始時刻到結束時刻）不能有交叉，則，我們加入新任務時，要把該時刻左邊的所有時間段全部去掉，因為他們已經處理完畢，處理的時候要恢復計算機的算力，然后再把新任務加入計算機中處理，因此我們可以用堆來維護每一臺計算機的狀態，
2.判斷該計算機算力是否大于等于該任務的消耗算力，
代碼
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
#define x first
#define y second
int n, m;
int w[N];
priority_queue<PII, vector<PII>, greater<PII> > q[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> w[i];//輸入每個計算機的算力
while(m --){
int a, b, c, d;
cin >> a >> b >> c >> d;
while(q[b].size() && q[b].top().x <= a){//洗掉計算機 b 已經結束的任務
PII t = q[b].top();
q[b].pop();
w[b] += t.y;//恢復計算機 b 算力
}
if(w[b] < d) cout << "-1" << endl;//計算機 b 算力不足
else {//可以加入該任務
q[b].push({a + c, d});
w[b] -= d;
cout << w[b] << endl;//輸出計算機 b 剩余算力
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/300910.html
標籤：其他
上一篇：HCNP Routing&Switching之IS-IS路由聚合和認證
下一篇：Qunar 云原生容器化落地實踐