思路
对每个计算机维护一个堆,堆中存每一个任务对应的<任务结束时刻,消耗的算力>,
当在ai时刻分配任务d,则把堆中任务结束时刻小于ai的全部弹出\恢复算力,
然后加入当前任务d(要判断能否加入)即可.
/*
* @Author: ACCXavier
* @Date: 2021-05-14 08:37:10
* @LastEditTime: 2021-05-14 08:55:44
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/problem/content/description/3495/
* @keywords:
有 n 台计算机,第 i 台计算机的运算能力为 vi。
有一系列的任务被指派到各个计算机上,第 i 个任务在 ai 时刻分配,指定计算机编号为 bi,耗时为 ci 且算力消耗为 di。
如果此任务成功分配,将立刻开始运行,期间持续占用 bi 号计算机 di 的算力,持续 ci 秒。
对于每次任务分配,如果计算机剩余的运算能力不足则输出 −1,并取消这次分配,否则输出分配完这个任务后这台计算机的剩余运算能力。
输入格式
输入的第一行包含两个整数 n,m,分别表示计算机数目和要分配的任务数。
第二行包含 n 个整数 v1,v2,⋅⋅⋅vn,分别表示每个计算机的运算能力。
接下来 m 行每行 4 个整数 ai,bi,ci,di,意义如上所述。数据保证 ai 严格递增,即 ai<ai+1。
输出格式
输出 m 行,每行包含一个数,对应每次任务分配的结果。
数据范围
对于 20% 的评测用例,n,m≤200。
对于 40% 的评测用例,n,m≤2000。
对于所有评测用例,1≤n,m≤200000,1≤ai,ci,di,vi≤109,1≤bi≤n。
输入样例:
2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4
输出样例:
2
-1
-1
1
-1
0
样例解释
时刻 1,第 1 个任务被分配到第 1 台计算机,耗时为 5,这个任务时刻 6 会结束,占用计算机 1 的算力 3。
时刻 2,第 2 个任务需要的算力不足,所以分配失败了。
时刻 3,第 1 个计算机仍然正在计算第 1 个任务,剩余算力不足 3,所以失败。
时刻 4,第 1 个计算机仍然正在计算第 1 个任务,但剩余算力足够,分配后剩余算力 1。
时刻 5,第 1 个计算机仍然正在计算第 1,4 个任务,剩余算力不足 4,失败。
时刻 6,第 1 个计算机仍然正在计算第 4 个任务,剩余算力足够,且恰好用完。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 200010;
int n,m;
int s[N];//每台计算机算力
priority_queue<PII,vector<PII>,greater<PII> >q[N];//每台计算机任务
//PII <结束时刻,算力>
//!要小根堆
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i)scanf("%d",&s[i]);//!下标从1开始
while (m -- ){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
while(q[b].size()&&q[b].top().x<=a){//当堆尾的结束时刻小于当前分配时刻
s[b] += q[b].top().y;//!恢复算力 +
q[b].pop();//弹出该任务
}
if(s[b]<d)puts("-1");//当前算力无法分配
else{
q[b].push({a+c,d});//加入任务
s[b] -= d;//更新算力
printf("%d\n",s[b]);//输出算力
}
}
return 0;
}
即所谓
银行家算法
爱了。你不说我都不知道。
蓝桥杯的题,我想复杂了。。。用树状数组做的
好家伙我也是,直接都离线查询了,1132ms莽过去了
比堆快多了,堆得$4000$多$ms$,$1132$是所有数据一起的,不是一组数据
堆也1000多毫秒,你用的cin吧
确实
评论区的大佬们你们到底在说什么😵
orZZZZZZZZZZZZZZZZ
tql!
为什么还要回复算力?
牛
tql