第十二届蓝桥杯省赛第二场C++A/B组 负载均衡
2021/9/17 9:04:48
本文主要是介绍第十二届蓝桥杯省赛第二场C++A/B组 负载均衡,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目大意:
给定 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; }
这篇关于第十二届蓝桥杯省赛第二场C++A/B组 负载均衡的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享