溪染的排列P
正解思路
考虑对比a和b
a和b要么有1个地方不同,要么有2个地方不同
分类讨论即可
复杂度o(n)
#include<bits/stdc++.h> using namespace std; const int N=1005; int n; int cnt; int p[N]; int pos[N]; bool vis[N]; int a[N],b[N]; int s1[N],s2[N]; int main() { scanf("%d",&n); for(int i=1; i<=n; ++i) scanf("%d",&a[i]),s1[a[i]]++; for(int i=1; i<=n; ++i) scanf("%d",&b[i]),s2[b[i]]++; for(int i=1; i<=n; ++i) if(a[i]!=b[i]) pos[++cnt]=i; if(cnt==2) { for(int i=1; i<=n; ++i) p[i]=a[i]; p[pos[1]]=b[pos[1]]; cnt=0; for(int i=1; i<=n; ++i) { if(!vis[p[i]]) ++cnt; vis[p[i]]=1; } if(cnt==n) for(int i=1; i<=n; ++i) printf("%d ",p[i]); else { p[pos[1]]=a[pos[1]]; p[pos[2]]=b[pos[2]]; for(int i=1; i<=n; ++i) printf("%d ",p[i]); } } else { for(int i=1; i<=n; ++i) { if(i==pos[1]) { for(int j=1; j<=1000; ++j) if(!s1[j]&&!s2[j]) { printf("%d ",j); break; } } else printf("%d ",a[i]); } } return 0; }
验题人代码
#include<bits/stdc++.h> using namespace std; int a[1005],b[1005]; int p[1005]; int n; void check() { int pa=0,pb=0; for(int i=1;i<=n;i++){ if(p[i]!=a[i]) pa++; if(p[i]!=b[i]) pb++; } if(pa==1&&pb==1){ for(int i=1;i<=n;i++) cout<<p[i]<<" "; exit(0); } return; } int vis[1005]; int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) if(a[i]==b[i]&&!vis[a[i]]){ vis[a[i]]=1; p[i]=a[i]; } int x=0,y=0; for(int i=1;i<=n;i++) if(!p[i]){ if(!x) x=i; else y=i; for(int j=1;j<=n;j++) if(!vis[j]){ vis[j]=1; p[i]=j; break; } } check(); swap(p[x],p[y]); check(); return 0; }