题目描述

FJ又有n(1<=n<=500)头奶牛都有一个或一个以上的朋友。FJ记录每头牛的朋友数，但他傻不小心混入了一个错的数字，请找出。

输入格式

* Line 1: The integer N.

* Lines 2..2+N: Line i+1 contains the number of friends for one of FJ's cows, or possibly the extra erroneous number.

输出格式

* Line 1: An integer K giving the number of entries in FJ's list that could be the extra number (or, K=0 means that there is no number on the list whose removal yields a feasible pairing of friends).

* Lines 2..1+K: Each line contains the index (1..N+1) within the input ordering of a number of FJ's list that could potentially be the extra number -- that is, a number that can be removed such that the remaining N numbers admit a feasible set of

friendships among the cows. These lines should be in sorted order.

输入输出样例

输入

4 

1 

2 

2 

1 

3 

输出

3 1 4 5

题解

注意到n很小

我们可以枚举哪个数字出错了。转为对剩下数字的判定性问题。

容易发现我们要判断的是一个图的合法性：给出每个点的度判断能否构成。

我们可以设想，连边必然是先连出度大的，再连出度小的（如果你先连出度小的。你出度大的边的选择就少了。那么方案的构造就很容易失败了。）

于是我们每次连完一个点之后就排一次序。直至整个序列为0.

可以用桶时间复杂度O（n^3）实现

 

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=505;
 6 int n,a[N],t[N],p[N],m,ans[N],tot;
 7 inline bool check()
 8  {for(int i=m;i>0;i--) 
 9     while(t[i])
10       {int cnt=i; t[i]--;
11        for(int i=0;i<=m;i++) p[i]=t[i];
12        
13        for(int k=i;k>0;k--)
14            {while(p[k])
15              {if(cnt==0) break;
16             p[k]--; t[k]--;  t[k-1]++;
17             cnt--; 
18              }
19             if(cnt==0) break; 
20            }
21            
22            
23       if(cnt>0) return 0;      
24       }
25   return 1;          
26  }
27 int main()
28  {
29  scanf("%d",&n);n++;
30  for(int i=1;i<=n;i++) {scanf("%d",&a[i]); m=max(m,a[i]);}    
31      
32  for(int x=1;x<=n;x++)    
33   {memset(t,0,sizeof(t));
34    for(int i=1;i<=n;i++) if(x!=i) t[a[i]]++;
35    
36    if(check()) ans[++tot]=x;  
37    
38   }
39  printf("%d\n",tot);
40  for(int i=1;i<=tot;i++) printf("%d\n",ans[i]);     
41 return 0;
42  }