CodeForces1481C
题意
有一个围栏，每一块上都有颜色，用A数组来表示，Bob觉得太单调了，他想涂成B数组的颜色。这时候有m个粉刷匠，每个粉刷匠能且只能粉刷一次围栏，问你通过这m个人的粉刷能否达到Bob的要求。如果可以输出YES，并把每个粉刷匠粉刷的下标输出，否则输出NO。
思路
本题需要思考的地方在这：对于最后一个元素，如果b数组中不存在和最后一个相同的元素，那么无论如何也满足不了要求。而且如果C数组出现了B数组中不期望的元素，那么这些元素尽量要涂在同一个元素上，而且被涂的元素后面要出现，例如样例1的第三个case。
还一个需要注意的地方是最后查询的时候要倒序查询，为什么要倒序？对于
2 2 2
2 2 2
2 3 2
这组样例，对于3这个颜色，B数组中并没有出现，我们要把它粉刷在他后面那个人可以粉刷的颜色上。
想通了以上两点，是模拟去实现了，这里贴一个简洁的代码实现。
AC代码
-
#include<bits/stdc++.h>
-
using namespace std;
-
const
int maxn =
1e5+
10;
-
int a[maxn];
-
int b[maxn];
-
int c[maxn];
-
vector<
int> v[maxn];
-
int main(void){
-
int t;
-
cin >> t;
-
while(t--){
-
int n,m;
-
cin >> n >> m;
-
for(
int i =
1; i <= n; i++) cin >> a[i];
-
for(
int i =
1; i <= n; i++) cin >> b[i];
-
for(
int i =
1; i <= m; i++) cin >> c[i];
-
int flag =
0;
-
for(
int i =
1; i <= n; i++){
-
if(b[i]==c[m]) flag = i;
-
}
-
if(flag==
0){
-
cout<<
"NO"<<endl;
-
continue;
-
}
-
int cnt =
0;
-
for(
int i =
1; i <= n; i++){
-
if(a[i]!=b[i]){
-
v[b[i]].push_back(i);
-
cnt++;
-
}
-
}
-
vector<
int> ans;
-
for(
int i = m; i >=
1; i--){
-
if(v[c[i]].size()==
0){
-
if(i==m) ans.push_back(flag);
-
else ans.push_back(ans[
0]);
-
continue;
-
}
-
ans.push_back(v[c[i]].back());
-
v[c[i]].pop_back();
-
cnt--;
-
}
-
if(cnt) cout<<
"NO"<<endl;
-
else{
-
cout<<
"YES"<<endl;
-
reverse(ans.begin(),ans.end());
-
for(auto x:ans) cout<<x<<
" ";
-
cout<<endl;
-
}
-
for(
int i =
1; i<= n; i++) v[i].clear();
-
}
-
return
0;
-
}
注意：多组Test，容器一定要清空！！！
转载：https://blog.csdn.net/wxd1233/article/details/113733634
查看评论