CSP CCF： 202203-3 计算资源调度器 （C++）
目录题目来源问题描述题目背景问题描述输入格式输出格式样例输入样例输出样例解释子任务解题思路代码题目来源计算机软件能力认证考试系统问题描述试题编号：202203-3试题名称：计算资源调度器时间限制：1.0s内存限制：512.0MB问题描述：题目背景西西艾弗岛上兴建了一批数据中心，建设了云计算资源平台。小 C 是主管西西艾弗云开发的工程师。西西艾弗云中...
问题描述
| 试题编号： | 202203-3 | |||||||||||||||||||||||||||||||||||||||||||||
| 试题名称： | 计算资源调度器 | |||||||||||||||||||||||||||||||||||||||||||||
| 时间限制： | 1.0s | |||||||||||||||||||||||||||||||||||||||||||||
| 内存限制： | 512.0MB | |||||||||||||||||||||||||||||||||||||||||||||
| 问题描述： | 题目背景西西艾弗岛上兴建了一批数据中心，建设了云计算资源平台。小 C 是主管西西艾弗云开发的工程师。西西艾弗云中有大量的计算节点，每个计算节点都有唯一编号。 西西艾弗云中运行的计算任务分为不同的应用，每个计算任务都有一个应用与之对应，一个应用中可能包括多个计算任务。 下图示意性地说明了可用区、计算节点、计算任务之间的关系，同时也说明了应用和计算任务的对应关系。
一开始，小 C 使用了电子表格程序来统计计算任务的分配情况。随着云上的计算节点和计算任务的不断增多，小 C 被这些奇怪的要求搞得焦头烂额，有的时候还弄错了安排，让客户很不满意。 问题描述计算任务对计算节点的要求十分复杂而且又不好描述，你对小 C 表示写程序这件事很为难。于是，小 C 进行了调研，
小 C 要求你按照如下方法来分配计算节点：按照计算任务的启动顺序，根据要求，依次为每个计算任务选择计算节点。一旦选择了一个计算节点，就固定下来不再变动，
输入格式输入的第一行包含两个由空格分隔的正整数 n 和 m，分别表示计算节点的数目和可用区的数目。计算节点从 1 到 n 编号，可用区从 1 到 m 编号； 输入的第二行包含 n 个由空格分隔的正整数 l1,l2,…li,…,ln，表示编号为 i 的计算节点位于编号为 li 的可用区。其中，0<li≤m； 输入的第三行包含一个正整数 g，表示计算任务的组数； 接下来的 g 行，每行包含六个由空格分隔的整数 fi、ai、nai、pai、paai、paari，表示依次启动的一组计算任务的信息，其中：
计算任务按组输入实际上是一种简化的记法，启动一组 (fi,ai,nai,pai,paai,paari) 和连续启动 fi 组 (1,ai,nai,pai,paai,paari) 并无不同。 输出格式输出 g 行，每行有 fi 个整数，由空格分隔，分别表示每个计算任务被分配的计算节点的情况。若该计算任务没有被分配，则输出 0；否则输出被分配的计算节点的编号。 样例输入Data 样例输出Data 样例解释本输入中声明了十个计算节点，前五个位于可用区 1，后五个位于可用区 2。可用区 3 和 4 不包含任何计算节点。 对于第一组计算任务，由于它们声明了计算节点亲和性要求，但要求的可用区编号是 4，该可用区不包含计算节点，因此都不能满足。 对于第二组计算任务，要在可用区 1 中启动 6 份应用 1 的任务，并且要求了计算任务反亲和性。因此，前五份任务分别被安排在前五个节点上。对于第六份任务，由于它必须运行于可用区 1，所以能够安排的范围仅限于前五个节点。但是它还指定了强制的计算任务反亲和性，前五个节点上已经启动了属于应用 1 的计算任务，因此没有能够运行它的节点。 对于第三组计算任务，要在可用区 2 中启动 1 份应用 2 的任务，直接将其分配给节点 6。 对于第四组计算任务，要在可用区 2 中启动 6 份应用 1 的任务，并且要求了计算任务反亲和性，不能和应用 2 的计算任务分配在同一个节点上。因此，节点 6 不能用于分配，这六份任务只能分配在节点 7～10 上。按照题意，选取运行任务数最少的和编号最小的，因此依次分配 7、8、9、10、7、8。 对于第五组计算任务，要在可用区 2 中启动 5 份应用 2 的任务，并且要求了尽量满足的计算任务反亲和性，不能和应用 1 的计算任务分配在同一个节点上。此时，可用区 2 中的节点 6 上没有应用 1 的计算任务，因此这 5 份计算任务都会被分配到这个节点上。 对于第六组计算任务，要启动 11 份应用 3 的任务，并且要求了尽量满足的计算任务反亲和性，不能和应用 3 的其它计算任务分配在同一个节点上，同时要求和应用 1 的计算任务位于同一个可用区。应用 1 位于两个可用区，因此全部 10 个节点都可以用于分配。对于前 10 份任务，按照题意，依次选取运行的任务数最少且编号最小的节点进行分配。对于第 11 份任务，由于所有的节点上都运行有应用 3 的任务，因此没有节点符合它的反亲和性要求。又因为反亲和性要求是尽量满足的，因此可以忽略这一要求，将它安排在节点 1 上。 子任务本题包含 20 个测试用例，每个 5 分。 全部测试数据保证 0<m≤n≤1000，0<g≤∑i=1gfi≤2000。 部分测试点的特殊性质详见下表，比如测试点 1、2 中最大应用编号仅为 10 且不包含任何需求。
|
解题思路
耐心看题，根据题目描述来写
写之前先看一下最后的子任务部分，慢慢增加相应的功能。
代码
20分版本
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m; // 计算节点的数目和可用区的数目
cin>>n>>m;
for (int i = 1; i <= n; ++i) {
int li;
cin>>li;
}
int g; // 任务的组数
cin>>g;
int index = 0;
for (int i = 0; i < g; ++i) {
int f, a, na, pa, paa, paar;
cin>>f>>a>>na>>pa>>paa>>paar;
if (na == 0 && pa == 0 && paa == 0) { // 不需要满足任何要求时
for (int j = 0; j < f; ++j) {
index = (index % n) + 1;
cout<<index<<" ";
}cout<<endl;
}
else {
}
}
return 0;
}
50分版本
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main()
{
int n, m; // 计算节点的数目和可用区的数目
cin>>n>>m;
vector<vector<int> > area2node(m + 1); // [可用区编号： [节点编号]]
vector<int> node2area(n + 1); // [节点编号： 可用区编号]
for (int i = 1; i <= n; ++i) {
int li;
cin>>li;
area2node[li].emplace_back(i);
node2area[i] = li;
}
int g; // 任务的组数
cin>>g;
vector<map<int, int> > node2appl(n + 1); // [节点编号： {应用编号， 任务数}]
vector<int> node2tasknum(n + 1, 0);
int index = 0, mintasknum = 0; // 记录下标（这个其实可以省掉的）、节点最小任务数
for (int i = 0; i < g; ++i) {
int f, a, na, pa, paa, paar;
cin>>f>>a>>na>>pa>>paa>>paar;
if (na == 0 && pa == 0 && paa == 0) { // 不需要满足任何要求时
while (f != 0) { // 寻找满足当前条件的节点编号
index = (index % n) + 1;
if (mintasknum == node2tasknum[index]) { // 当前节点任务数是最少的就用它
cout<<index<<" ";
node2tasknum[index]++;
node2appl[index][a]++;
f--;
}
if (index == n) { // 全部找了一轮了，没有节点的任务数等于它时， mintasknum需要+1
mintasknum++;
}
}
}
else if (na != 0 && pa == 0 && paa == 0) { // 只需要满足计算节点亲和性（在指定的可用区上）
int curmintasknum = mintasknum;
if (area2node[na].size() == 0) { // 当前区无节点
//cout<<"I' here"<<endl;
while (f != 0) {
cout<<0<<" ";
f--;
}
}
else { // 当前区有节点
while (f != 0) {
for (int node: area2node[na]) { // 对于处于该区的每一个节点
if (node2tasknum[node] == curmintasknum) {
cout<<node<<" ";
node2tasknum[node]++;
node2appl[node][a]++;
f--;
}
if (f == 0) {
break;
}
}
curmintasknum ++;
}
}
}
else {
}
cout<<endl;
}
return 0;
}
---------------------------------------- 更新 ------------------------------------------
55分 (拿不到80，看不出代码的毛病，头秃...）
#include <iostream>
#include <map>
#include <vector>
using namespace std;
// 存在满足条件的节点时
void f1(int f, vector<int> nodes, int mintasknum, int a, vector<map<int, int> > &node2appl, vector<int> &node2tasknum) {
while (f != 0) {
for (int node: nodes) {
if (mintasknum == node2tasknum[node]) {
cout<<node<<" ";
node2tasknum[node]++;
node2appl[node][a]++;
//appl2node[a].emplace_back(node);
f--;
}
if (f == 0) {
break;
}
}
mintasknum ++;
}
}
// 不存在满足条件的节点时
void f2(int f) {
for (int i = 1; i <= f; ++i) {
cout<<0<<" ";
}
}
int main()
{
int n, m; // 计算节点的数目和可用区的数目
cin>>n>>m;
vector<vector<int> > area2node(m + 1); // [可用区编号： [节点编号]]
//vector<int> node2area(n + 1); // [节点编号： 可用区编号]
for (int i = 1; i <= n; ++i) {
int li;
cin>>li;
area2node[li].emplace_back(i);
//node2area[i] = li;
}
int g; // 任务的组数
cin>>g;
vector<map<int, int> > node2appl(n + 1); // [节点编号： {应用编号， 任务数}]
//map<int, vector<int> > appl2node; // [应用编号：[节点编号]]
vector<int> node2tasknum(n + 1, 0); // [节点编号： 任务总数]
for (int i = 0; i < g; ++i) {
int f, a, na, pa, paa, paar;
cin>>f>>a>>na>>pa>>paa>>paar;
// 符合要求的节点编号
vector<int> nodes;
// 节点最小任务数
int mintasknum = INT_MAX;
for (int index = 1; index <= n; ++index) { // 不要将index写成 i ！！！
if (mintasknum > node2tasknum[index]) {
mintasknum = node2tasknum[index];
}
}
if (na == 0 && pa == 0 && paa == 0) { // 不需要满足任何要求时
for (int index = 1; index <= n; ++index) { // 记录符合要求的节点编号
nodes.emplace_back(index);
}
f1(f, nodes, mintasknum, a, node2appl, node2tasknum);
}
else if (na != 0 && pa == 0 && paa == 0) { // 只需要满足计算节点亲和性（在指定的可用区上）
nodes = area2node[na]; // 记录符合要求的节点编号
if (nodes.size() == 0) { // 当前区无节点
f2(f);
}
else { // 当前区有节点
f1(f, nodes, mintasknum, a, node2appl, node2tasknum);
}
}
else if (na == 0 && pa == 0 && paa != 0) { // 只需要满足计算任务反亲和性（不能和指定应用在同一节点）
for (int index = 1; index <= n; ++index) { // 记录符合要求的节点编号
if (node2appl[index].count(paa) == 0) {
nodes.emplace_back(index);
}
}
if (nodes.size() != 0) { // 存在这样的节点
f1(f, nodes, mintasknum, a, node2appl, node2tasknum);
}
else if (paar == 1) { // 不存在满足条件的节点，并且必须paa时
f2(f);
}
else { // 不存在满足条件的节点，并且尽量满足paa时， 就相当于去掉这个条件
vector<int> nodes1;
for (int index = 1; index <= n; ++index) { // 记录符合要求的节点编号
nodes1.emplace_back(index);
}
f1(f, nodes1, mintasknum, a, node2appl, node2tasknum);
}
}
else if (na != 0 && pa == 0 && paa != 0) { // 同时满足 计算节点亲和性 & 计算任务反亲和性
vector<int> nodes1;
// 先找出符合 计算节点亲和性的节点
nodes1 = area2node[na];
// 再找出符合 计算任务反亲和性的节点
for (int node: nodes1) {
if (node2appl[node].count(paa) == 0) {
nodes.emplace_back(node);
}
}
// 进行与计算任务反亲和性 一样的操作
if (nodes.size() != 0) { // 存在这样的节点
f1(f, nodes, mintasknum, a, node2appl, node2tasknum);
}
else if (paar == 1) { // 不存在满足条件的节点，并且必须paa时
f2(f);
}
else { // 不存在满足条件的节点，并且尽量满足paa时， 就相当于没有 计算任务反亲和性 条件限制了
if (nodes1.size() != 0) { // !!!
f1(f, nodes1, mintasknum, a, node2appl, node2tasknum);
}
else {
f2(f);
}
}
}
else {
}
cout<<endl;
}
return 0;
}
-------------------------------- 更新 -----------------------------------------
找到只有55分的原因啦！ 主要是因为忽略了 计算任务反亲和性 的一些细节：
当paa != 0 && paa == a时：
a、paar==1： 每次循环完当前的nodes，就得筛一遍，去掉那些加入了应用a的节点。直至 f == 0， 结束这句任务。或者 nodes==0，就将剩余的 f 输出为 0。
b、paar == 0： 每次循环完当前的nodes，就得筛一遍，去掉那些加入了应用a的节点。直至 f == 0， 结束这句任务。或者 nodes==0，此时得考虑去除 计算任务反亲和性 条件过滤后是否存在节点，不存在，则输出0，存在则将nodes更改成去除此条件过滤后得到的节点，每次循环完不用再筛了。
80分， 没拿到100， 现在是内存超了， 不晓得有没有其它问题
（大改了一下代码， 将一些一块一块的代码做成了函数。这样应该更容易理解。 考试的时候也应该像这样将不同的功能分成不同的函数，这样方便调试，也方便根据子任务来逐个完善、得分）
#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
void cond1(int na, vector<int> &nodes, vector<vector<int> > &area2node) {
nodes = area2node[na];
}
void cond2(int n, int na, int pa,
vector<int> &nodes, vector<vector<int> > &area2node, map<int, set<int> > &appl2area) {
vector<int> newNodes;
vector<int> cur, areas;
areas.assign(appl2area[pa].begin(), appl2area[pa].end());
for (int area: areas) {
for (int node: area2node[area]) {
cur.emplace_back(node);
}
}
sort(cur.begin(), cur.end()); // 排序！！！
if (na == 0) {
nodes = cur;
}
else if (nodes.size() != 0) {
unsigned int index_n = 0, index_c = 0;
while(index_c < cur.size() && index_n < nodes.size()) {
if (nodes[index_n] == cur[index_c]) {
newNodes.emplace_back(index_c);
}
else if (nodes[index_n] > cur[index_c]) {
index_c ++;
}
else {
index_n ++;
}
}
nodes = newNodes;
}
// else nodes.size() == 0
}
void cond3(int paa, int paar, vector<int> &nodes, vector<map<int, int> > &node2appl) {
vector<int> newNodes;
for (int node: nodes) {
if (node2appl[node].count(paa) == 0) {
newNodes.emplace_back(node);
}
}
nodes = newNodes;
}
// 获取现有节点最少任务数
int getMintasknum(vector<int> &nodes, vector<int> &node2tasknum) {
int mintasknum = INT_MAX;
for (int node: nodes) { // 不要将index写成 i ！！！
if (mintasknum > node2tasknum[node]) {
mintasknum = node2tasknum[node];
}
}
return mintasknum;
}
// 过滤后没有满足条件的节点时
void f2(int f) {
for (int i = 1; i <= f; ++i) {
cout<<0<<" ";
}
}
// 过滤后有满足条件的节点时
void f1(int f, vector<int> &nodes, vector<int> &nodes_, int a, int paa, int paar,
vector<map<int, int> > &node2appl, vector<int> &node2tasknum, map<int, set<int> > &appl2area, vector<int> &node2area) {
int mintasknum = getMintasknum(nodes, node2tasknum); // 获取现有节点最少任务数
bool flag = true; // 记录是不是恢复到了nodes_
while (f != 0) {
/*
cout<<endl<<" *** Nodes = ";
for (int node: nodes) {
cout<<node<<" ";
}cout<<endl;
*/
for (int node: nodes) {
if (mintasknum == node2tasknum[node]) {
cout<<node<<" ";
node2tasknum[node]++;
node2appl[node][a]++;
appl2area[a].insert(node2area[node]);
f--;
}
if (f == 0) {
break;
}
}
mintasknum ++;
if (flag == true && paa != 0 && paa == a && nodes.size() != 0) { // 更新 node2appl
cond3(paa, paar, nodes, node2appl);
// 如果nodes中没有节点了， 并且（是强制不能和a在一个节点 或者 nodes_也为空），输出0
if (nodes.size() == 0 && (paar == 1 || nodes_.size() == 0)) {
f2(f);
return ;
}
}
// // nodes中没有节点了， 不是必须不能和应用a在一起，就恢复至取消条件三的情况下
if (paa != 0 && paa == a && paar == 0 && nodes.size() == 0) {
nodes = nodes_;
mintasknum = getMintasknum(nodes, node2tasknum); // 获取现有节点最少任务数
flag == false;
}
}
}
int main()
{
int n, m; // 计算节点的数目和可用区的数目
cin>>n>>m;
vector<int> originalN(n);
for (int i = 0; i < n; ++i) {
originalN[i] = i+1;
}
vector<vector<int> > area2node(m + 1); // area2node[可用区编号] ：[节点编号 i ,....]
vector<int> node2area(n+1); // node2area[节点编号] :可用区编号
for (int i = 1; i <= n; ++i) {
int li;
cin>>li;
area2node[li].emplace_back(i);
node2area[i] = li;
}
int g; // 任务的组数
cin>>g;
vector<map<int, int> > node2appl(n + 1); // node2appl[节点编号]： {应用编号i， 任务数 } ....
vector<int> node2tasknum(n + 1, 0); // node2tasknum[节点编号]： 任务总数
map<int, set<int> > appl2area; // appl2area {应用编号： {可用区编号}, .....}
for (int i = 0; i < g; ++i) {
int f, a, na, pa, paa, paar;
cin>>f>>a>>na>>pa>>paa>>paar;
// 符合要求的节点编号
vector<int> nodes = originalN;
vector<int> nodes_;
// 计算节点亲和性
if (na != 0) {
cond1(na, nodes, area2node);
}
// 计算任务亲和性
if (pa != 0) {
cond2(n, na, pa, nodes, area2node, appl2area);
}
// 计算任务反亲和性
nodes_ = nodes;
if (paa != 0) {
cond3(paa, paar, nodes, node2appl);
if (paar == 0 && nodes.size() == 0) { // 当条件三非强制满足并且nodes.size() == 0时， node还原成上一步的nodes
nodes = nodes_;
}
}
// 输出chu筛过的节点编号
if (nodes.size() == 0) {
f2(f);
}
else {
f1(f, nodes, nodes_, a, paa, paar, node2appl, node2tasknum, appl2area, node2area);
}
cout<<endl;
}
return 0;
}
华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
更多推荐
10
0- 0
已为社区贡献1条内容
所有评论(0)