你缺什么（codevs 2928）

2928 你缺什么

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题解

题目描述 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。数据由随机数产生。

数据太弱了，回溯都能过！！！

#include<cstdio>

#include<iostream>

#define M 10010

using namespace std;

int a[M],vis[M],q[M],n,flag;

void dfs(int t)

{

    if(flag)return;

    if(t>n)

    {

        for(int i=;i<=n;i++)

          printf("%d ",q[i]);

        flag=;

    }

    for(int i=;i<=n;i++)

      if(!vis[i]&&a[i]!=a[q[t-]])

      {

          q[t]=i;

          vis[i]=;

          dfs(t+);

          vis[i]=;

          q[t]=;

      }

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

      scanf("%d",&a[i]);

    q[]=;

    vis[]=;

    dfs();

    return ;

}

巴特西

你缺什么（codevs 2928）

2928 你缺什么

最新文章

热门文章