2022-03-3 计算资源调度器 stl大模拟使用map优化索引
- 2022-03-3 计算资源调度器 stl大模拟使用map优化索引
- 思路
- 写代码的过程（遇到的问题）
- 完整代码
2022-03-3 计算资源调度器 stl大模拟使用map优化索引
在联系了之前那么多道stl大模拟题后，终于能够独自在一定的时间内完成第三题了，不过这题算是比较简单的，因为我是倒着练习的，先练习的是最新的题目，但是csp的趋势是，前2题越来越简单，然后第三题越来越难，所以我做的这题算是在第三题中比较简单的。
从开始看题到100分
但是不管难度如何第三题的思路都是使用STL中的数据结构，并且没有什么算法的，然后就是注意一些细节问题就可以拿到满分，所以不要觉得第三题很难。
一是有信心，二是能想到对应的数据结构，三是能够注意细节。这样拿下第三题就不在话下（当然我还没有拿下）
思路
这题的思路之前的题目都是大差不差的，看似题目的背景有些差别，但是思路非常相似。
首先题目有四个数据类型
一是可用区：可用区可以包含多个计算节点，每个可用区有唯一的编号
二是计算节点：计算节点是包含在可用区里的，每个计算节点含有多个应用
三是应用：就是包含在计算节点中的，每个计算任务都要有一个应用执行
四是计算任务：计算任务可以有一些需求来限制要放在哪个可用区，哪个计算节点上的。
然后每个我们就可以使用map来建立映射关系（本质上是建立索引方便搜索的）
最后任务就是为任务搜索出符合限制条件的计算节点，然后输出就好了。
写代码的过程（遇到的问题）
首先做第三题最好不要一口吃一个胖子，就是一步一步的写，一个一个测试点的过，这样找错误比较容易。如果全部写完然后再找错误很容易会被混淆，很难定位错误在哪里。
- 首先不考虑限制条件（对应测试点1，2，3，4）
主要就是排序问题 按着题目给的排序要求来写，选出来最合适的计算节点然后更新
这里我写完了还是0分
然后发现最后选出来了最适合的节点，但是没有更新它，让其包含这个计算任务
然后就20分了
- 然后考虑有可用区亲和性的限制（对应测试点 5，6，7，8，9，10）
这里写好了代码，但是还是20分
然后检查错误，发现是没有判断特殊情况，如果可用区没有节点可分配的情况下就输出0
if (na != 0) // 如果有可用区亲和性
{
alloc = part[na].nodein;
alloc_part.insert(na);
if (alloc.empty())
{
cout << 0 << ' ';
continue;
}
have_app = part[na].app_to_node[paa];
}
之后就50分了
- 然后写有节点反亲和性限制的代码（对应测试点11，12，13，14，15，16）
这个比较麻烦，写的时候发现代码结构有问题重构了结构（就是if else的结构），发现还是50分
然后发现代码有漏洞，就是如果根据这个反亲和性搜索出来的节点的集合是空的，那么如果是强制必须满足的话就要输出0然后跳出本次循环，但是如果不是强制满足的话，就不用这个条件删除，还用原来的。
这里我只判断了不是空的情况下，和是空并且强制满足的情况
if (!temp.empty())
alloc = temp;
else if (temp.empty() && paa == 1) // 如果要强制满足 但是又为空
{
cout << 0 << ' ';
continue;
}
这点看了我好久，很不容易发现，写代码不够规范，思路不够清晰导致的。
然后改成这样就好了
if (temp.empty() && paa == 1) // 如果要强制满足 但是又为空
{
cout << 0 << ' ';
continue;
}
if (!temp.empty())
alloc = temp;
然后还是50分，然后自己编了数据也没发现问题，后来就重新读题，发现原来是判断paar是不是必须满足，我笔误了一下，就找了很久的bug
将paa改成了paar
if (temp.empty() && paa == 1)改成了
if (temp.empty() && paar == 1)
然后就80分了，拼写错误真的很坑啊，很浪费时间啊，以后写if条件的时候要多想一下
- 增加应用亲和性的限制
这个限制，一开始读题没发现后来才发现是同一个区内要有相同的应用，而不是同一个计算节点上
然后这次写的比较顺利，把前面所有的问题都注意到了
一下就100分了
完整代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
// 计算节点
struct compute_node
{
int id;
int l; // 位于编号为l的可用区中
vector<int> app; // 节点中的计算应用
} node[1001];
// 计算区/可用区
struct compute_part
{
int id; // 编号
unordered_set<int> nodein; // 计算节点
map<int, unordered_set<int>> app_to_node; // 通过app的编号id找到计算节点的集合
} part[1001];
unordered_map<int, unordered_set<int>> app_to_allnode; /// 如果没有节点亲和性 从全局里面找应用亲和性
unordered_map<int, unordered_set<int>> app_to_part; //
unordered_set<int> all_compute_node;
bool cmp(struct compute_node a, struct compute_node b)
{
if (a.app.size() == b.app.size())
{
return a.id < b.id;
}
return a.app.size() < b.app.size();
}
int main()
{
// freopen("1.txt", "r", stdin);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> node[i].l;
node[i].id = i;
part[node[i].l].nodein.insert(i);
all_compute_node.insert(i);
}
int g;
cin >> g;
for (int i = 1; i <= g; i++)
{
int f, a, na, pa, paa, paar;
cin >> f >> a >> na >> pa >> paa >> paar;
for (int j = 1; j <= f; j++)
{
unordered_set<int> alloc; // 分配的节点
unordered_set<int> alloc_part; // 分配的区的编号
unordered_set<int> have_app; // 包含paa这个应用的节点
if (na != 0) // 如果有可用区亲和性
{
alloc = part[na].nodein;
alloc_part.insert(na);
if (alloc.empty())
{
cout << 0 << ' ';
continue;
}
have_app = part[na].app_to_node[paa];
}
else // 如果没有可用区亲和性
{
alloc = all_compute_node;
have_app = app_to_allnode[paa];
}
if (pa != 0) // 如果有应用亲和性 得在同一个区才行
{
unordered_set<int> hava_app_part = app_to_part[pa]; // 包含pa的可用区的集合
if (hava_app_part.empty())
{
cout << 0 << ' ';
continue;
}
if (!alloc_part.empty()) // 说明有可用区亲和性
{
for (auto item : alloc_part)
{
if (hava_app_part.count(item) == 0)
alloc_part.erase(item);
}
if (alloc_part.empty())
{
cout << 0 << ' ';
continue;
}
}
else // 说明没有可用区亲和性
{
alloc_part = hava_app_part;
have_app.clear();
alloc.clear();
for (auto item : alloc_part)
{
alloc.insert(part[item].nodein.begin(), part[item].nodein.end());
have_app.insert(part[item].app_to_node[paa].begin(), part[item].app_to_node[paa].end());
}
}
}
if (paa != 0) // 如果应用反亲和性
{
unordered_set<int> temp = alloc;
for (auto item : have_app)
{
temp.erase(item);
}
if (temp.empty() && paar == 1) // 如果要强制满足 但是又为空
{
cout << 0 << ' ';
continue;
}
if (!temp.empty())
alloc = temp;
}
struct compute_node min_node;
min_node.id = 0;
for (auto item : alloc)
{
if (min_node.id == 0 || cmp(node[item], min_node))
{
min_node = node[item];
}
}
node[min_node.id].app.push_back(a);
app_to_allnode[a].insert(min_node.id);
app_to_part[a].insert(min_node.l);
part[min_node.l].app_to_node[a].insert(min_node.id);
cout << min_node.id << ' ';
}
cout << endl;
}
return 0;
}
