题目描述 Description
继“你幸福吗”之后，央视又推出了“你缺什么”。而在采访过程中，记者发现了一些问题。
记者要采访n个人。已知第i个人要回答Ta缺某事物Xi，但如果Ta之前的一个人的答案和Ta一样，Ta就会改口。为了避免受访者改口，记者决定改变采访顺序。
现在给出这n个人的答案，请输出一种可行的方案。要求该方案字典序最小。数据保证有解。
输入描述 Input Description
第一行，一个数n。
接下来的n行，第i+1行为Xi。
输出描述 Output Description
一行，n个数，表示依次访问n个人的顺序。以空格隔开。
样例输入 Sample Input
10
1
5
4
1
4
2
1
3
3
5
样例输出 Sample Output
1 2 3 4 5 6 7 8 10 9
数据范围及提示 Data Size & Hint
0<n<=104，0<Xi<=5。数据由随机数产生。
分类标签 Tags 点此展开
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define N 10009 int a[N],b[N],ans[N],vis[N],n; void out(){ for(int i=1;i<=n;i++) printf("%d ",b[i]); puts(""); } void dfs(int i){ if(i<=n) for(int j=1;j<=n;j++) if(!vis[j]&&a[j]!=ans[i-1]){ b[i]=j;//记录答案 ans[i]=a[j];//记录a之前的一个人的答案 vis[j]=1; if(i==n){ out();exit(0);//只输出一次，不能是return } dfs(i+1); vis[j]=0; } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i); dfs(1); return 0; }