202203 CSP认证 | 计算资源调度器

本文主要是介绍202203 CSP认证 | 计算资源调度器，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计算资源调度器
还好还好，这个题目读懂题意然后做就好了，难度不高

两个亲和性都是对可用区域做出限制，而反亲和性是对计算节点做出限制。
先分别计算可用区域有哪些以及非法的计算节点有哪些（两个都很简单），然后再遍历在合法可用区域上的所有计算节点，如果在非法节点里面就continue，否则就加入到备选答案里面去。
如果此时ans，也就是备选答案为空，且paar = 0。则删去非法节点的限制，将所有合法可用区中的节点全部加入到备选答案里面去。最后就是搜索了。

acwing上面TLE了…但是平台上过了…BTW既然这样我就不管了
在这里插入图片描述

满分代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct task{  //计算任务ll app;    //运行在哪个应用上int area;  //运行在哪个可用区上int node;  //运行在哪个节点上
};
const int N = 1010; //计算节点和分区的最大数目
const int INF = 0x3f3f3f3f;
int n, m;
int node_count[N];  //每个计算节点运行的任务数量
int node_zone[N];   //为了读取开的一个数组
unordered_map<ll, vector<task> > AppTask;  //app上运行的计算任务
unordered_map<int, vector<int> > Zone;   //每个可用区上有哪些计算节点//对可用区域进行限制，找到所有合法的可用区
unordered_set<int> cal_pa(int na, ll pa)
{unordered_set<int> avai_zone;if(!AppTask.count(pa)){    //当前应用没有运行任何的计算任务return avai_zone;}vector<task> vec = AppTask[pa];  //找到当前应用下运行的所有计算任务for(int i = 0;i < vec.size();i ++){if(na){  //如果有节点亲和性if(vec[i].area == na){   //当前应用有计算任务运行在该可用区域上,此时满足两个条件avai_zone.insert(na);break;}}else{avai_zone.insert(vec[i].area); //所有计算任务的可用区都合法}}return avai_zone;
}
//找到所有的不合法节点
unordered_set<int> cal_paa(ll paa)
{unordered_set<int> unavai_node;if(AppTask.count(paa)){vector<task> vec = AppTask[paa];for(int i = 0;i < vec.size();i ++){  //遍历该应用上的每一个计算任务unavai_node.insert(vec[i].node);   //每一个任务的计算节点都为不合法节点}}return unavai_node;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for(int i = 1;i <= n;i ++){int x; cin >> x;Zone[x].push_back(i);node_zone[i] = x;}int f, na, paar, g;ll a, pa, paa;task temp;set<int> ans;  //因为需要节点的编号最小，这里用set而非unordered_setcin >> g;while(g --){cin >> f >> a >> na >> pa >> paa >> paar;bool flag = false; //对可用区是否有要求if(na || pa) flag = true;  //对可用区有要求while(f --){  //将每个任务独立处理-->主要是针对若paa = a的情况unordered_set<int> avai_zone;unordered_set<int> unavai_node;temp.app = a;if(pa) avai_zone = cal_pa(na, pa); //如果对pa&na || only pa有要求else if(na) avai_zone.insert(na);  //如果只对na有要求if(!avai_zone.size() && flag) {cout << "0 ";continue;}  //没有可用区满足要求,此时必然也没有节点满足要求if(paa)  unavai_node = cal_paa(paa);if(!flag){  //对可用区没有要求for(int i = 1;i <= n;i ++){if(unavai_node.count(i)) continue;  //只要不是非法计算节点都可ans.insert(i);}}else{for(auto az : avai_zone){  //遍历每一个可用区域for(auto node : Zone[az]){  //遍历该可用区中的每一个节点if(unavai_node.count(node)) continue;ans.insert(node);  //为合法的可用节点}}}if(!ans.size() && !paar){  //去掉反亲和性的要求for(auto az : avai_zone){for(auto node : Zone[az]){ans.insert(node);}}}if(!ans.size()) {cout << "0 "; continue;}//此时ans中留下来的都为筛选下来的合法节点int MAX = INF, index;for(auto node : ans){if(node_count[node] < MAX){MAX = node_count[node];index = node;}}cout << index << ' ';temp.node = index;temp.area = node_zone[index];AppTask[a].push_back(temp);node_count[index] ++;ans.clear();}cout << "\n";}return 0;
}