题目链接:CodeForces - 814B
题意:有两个序列,本来应该是1~n,但是都有一个数据错了,要求可能的原来序列。
题解:因为两个序列a,b都是只有一个错误,那么改变其中一个序列,就可以改回原来的序列。将b中与a不相同的数全部放入一个数组c中(注意c中只可能有一个或两个元素),将其它相同的数放入map中,以便于随时判断存在。如果c中只有一个元素的那么遍历一遍b数组,找出缺的数即可。如果c中有两个元素,那么根据四个待定元素(就是a,b中对应不相等的位置的元素)map中元素的存在性,可以确定错的那个数。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
map<int, int> m;
int main(){
int n, a[maxn], b[maxn], i, k = 0, p[maxn], c[maxn];
cin>>n;
for(i = 1; i <= n; i++) cin>>a[i];
for(i = 1; i <= n; i++){
cin>>b[i];
if(a[i] != b[i]) c[k++] = i; //记录不相同的数
else m[b[i]] = 1; //记录相同的数
}
if(k == 1){
for(i = 1; i <= n; i++){
if(m[i] == 0) b[c[0]] = i; //改为缺的数
}
}
else{
//b中却a的c[0]位元素,而b中的c[0]位已经有了或a[c[1]]已经重复了,就可以改了
if((m[a[c[0]]] == 0 && m[b[c[0]]] == 1) || m[a[c[1]]] == 1) b[c[0]] = a[c[0]];
else b[c[1]] = a[c[1]];
}
for(i = 1; i <= n - 1; i++) cout<<b[i]<<" "; cout<<b[i]<<endl;
return 0;
}