CSP202203_3
目录题目
思路
直接模拟，画个大致的分析图即可理清题目要求。
一个区上有多个节点，一个应用有多个任务。
一个任务只占用一个节点，多个任务可在一个节点上进行。
三种要求：
- 任务\(\in\)区
- 任务\(\in\)区 && 区上有特定应用的任务
- 任务\(\notin\) 节点 && 节点上有特定应用的任务
确定一系列任务，选择其最佳运行的节点。
确定维护的一定是节点的信息(因为所有操作都在节点上进行）。
考虑节点本身，首先应记录其自身编号，所属的区。
基于上述三种要求以及选择标准，我们还要记录节点运行任务总数、节点的所有任务所属应用。
使用 unordered_map 记录每个节点(具体原因后述)。
总体上就是分别针对三种需求，在所有节点中依次剔除不符合要求的节点，最后根据标准进行排序及选择。
一些问题
-
关于unordered_map：一开始直接采用的 map 维护，但结果是75pts(TLE)，借鉴了其他人写这道题的方法，使用 unordered_map 即可AC。
unordered_map因为不要求有序，因此使用哈希表维护，而map使用的是红黑树，显然数据量与操作很多时，unordered_map要快上不少
-
最后的排序问题，通过自定义比较函数，只能拿到80pts(TLE)，而类似处理中，他人博客通过重载运算符，使用 lambda 语句作为比较函数，则可AC。具体原因不太确定，
感觉可能是涉及到STL的一些底层实现？望dalao指点 -
关于迭代器的删除操作：vector 等序列性容器与 map 等关联性容器在删除迭代器指向内容后迭代器的变化是不同的，这次一定记住。
-
在最初模拟时，样例最后一个点总是错误，最终确定是在第三个要求的函数实现错误：
函数参数传递的只是vec而不是其引用。如果传引用，在进行第三步判断时，可能会导致vec1变空。
但实际若vec2由于非必须要求而可以不为空，所供选择的节点为为进行第三步判断的vec1，此处就会产生错误，将任务误判为无节点可用。
Code
80pts(直接按注释替换sort的比较部分即可AC)
#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch >'9')
{
if(ch == '-') f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x*f;
}
struct NODE
{
int id; //编号
int area; //所属区
int cnt; //运行任务数量
set <int> num; //运行任务所属应用的编号
// bool operator <(const NODE& a)const{
// if(this->cnt != a.cnt){
// return this->cnt < a.cnt;
// }
// else {
// return this->id < a.id;
// }
// }
};
int t, m;
vector <int> all;
unordered_map <int, NODE> node;
void Fun_1(int n, vector <int> &vec) //删除不满足节点亲和性的节点
{
//cout << "Fun1 Begin" << endl;
vector <int> :: iterator it = vec.begin();
while(it != vec.end())
{
if(node[*it].area != n)
{
it = vec.erase(it);
}
else it++;
}
return;
}
void Fun_2(int n, vector <int> &vec) //与编号为n的应用的任务在同一区
{
//cout << "Fun2 Begin" << endl;
set <int> mry; //记录可行的区
for(int i = 1; i <= node.size(); i++)
{
if(node[i].num.count(n))
{
mry.insert(node[i].area);
}
}
vector <int> :: iterator it = vec.begin();
while(it != vec.end())
{
if(!mry.count(node[*it].area))
{
it = vec.erase(it);
}
else it++;
}
return;
}
vector <int> Fun_3(int n, vector <int> vec)
{
//cout << "Fun3 Begin" << endl;
vector <int> :: iterator it = vec.begin();
while(it != vec.end())
{
if(node[*it].num.count(n))
{
it = vec.erase(it);
}
else it++;
}
return vec;
}
bool cmp(int a, int b)
{
if(node[a].cnt != node[b].cnt) return node[a].cnt < node[b].cnt;
else return node[a].id < node[b].id;
}
int main()
{
t = read(), m = read();
for(int i = 1; i <= t; i++)
{
int a = read();
node.insert(make_pair(i, NODE{i, a, 0, set<int>()}));
all.push_back(i);
//< 编号, {} >
}
int g = read();
while(g--)
{
int f = read(), a = read(), na = read();
int pa = read(), paa = read(), paar = read();
while(f--)
{
vector <int> vec1 = all, vec2;
if(na)
{
Fun_1(na, vec1);
}
if(pa)
{
Fun_2(pa, vec1);
}
if(paa)
{
vec2 = Fun_3(paa, vec1);
}
if(vec1.empty())
{
cout << 0 << " ";
continue;
}
if(vec2.empty())
{
if(paar)
{
cout << 0 << " ";
continue;
}
else
{
vec2 = vec1;
}
}
sort(vec2.begin(), vec2.end(), cmp);
// sort(vec2.begin(), vec2.end(), [](const auto& a, const auto& b)->bool{
// return node[a] < node[b];
// });
vector <int> :: iterator it = vec2.begin();
node[*it].cnt++;
node[*it].num.insert(a);
cout << node[*it].id << " ";
}
cout << endl;
}
return 0;
}
/*
10 4
1 1 1 1 1 2 2 2 2 2
6
2 1 4 1 2 1
6 1 1 0 1 1
1 2 2 0 0 0
6 1 2 0 2 1
5 2 2 0 1 0
11 3 0 1 3 0
*/