Description
FJ 的N 头奶牛(2<= N<= 500)都加入了社交网络“哞不可” 。
每头奶牛有一个或多个与它们自己在哞不可上互相关注的朋友。为了好玩,FJ 制作了一个列表,记下每头奶牛的朋友数目。但是,在书写列表的过程中,农夫John 惆怅了,以至于他错误地写下了一个额外的数字(因此他的列表包含N + 1 个数字,非他预计的N 个数字)。
请帮助FJ 找出在他的列表中有哪些数字可以是那个错误的额外数字。
第一行:整数N。
第2 至N + 2 行:第i + 1 行包含FJ 的某一头奶牛的朋友数量,或者也许是那个错误的额外数字。
Output
第一行:一个整数K 给出在FJ 的列表中有多少项目可能是那个额外的数字(或者,K = 0 意味着没有一个数字,移除后可以产生一个可行的朋友配对)。
第2 至K + 1 行:每行包含可能是额外的数字按照输入顺序产生的序号(1到N +1)——也就是说,一个移除后,剩下的N 个数字符合奶牛们某一个可行的朋友关系集合。这K 行的序号须按从小到大排列。
4
1
2
2
1
3
Sample Output
3
1
4
5
样例解释:
FJ 有4 头奶牛。两头每头只有一个朋友,两头各有两个朋友,还有一头有三个朋友(当然,这些数字其中一个是额外的并且不属于这个列表)。
移除FJ 列表的第一个数字(数字1)之后会得到一个剩下的数字2,2,1,3 组成的列表,并且符合一个可行的朋友关系配对——例如,如果我们将奶牛从A
到D 命名,那么配对(A;B); (A;C); (A;D) 以及(B;C) 就足够了,这是因为A有三个朋友,B 和C 都各有两个朋友,还有D 有一个朋友。同理,从FJ 的列表里移除另外一个“1”也是可行的,还有移除“3”也可以。从FJ 的列表里移除任意一个“2”都不可——我们可以看到剩下数字的和是奇数,明显我们无法凑出一个对应的配对。
Data Constraint
对于9% 的数据,N <=10。
对于27% 的数据,N <=100。
思路
假设删去了序列中的一个数,我们就需要知道如何判断剩下的数字是一个正确的关系。
对于降序排序后,最大的数字a[1]需要与后面的a[2]~a[a[1]+2]个成为朋友,最有的情况就是把前a[1]大都减一,所以我们需要每处理完最大的数字就排序,且最后结果全是0就是合法的。
#pragma GCC optimize(2)
#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[1000],b[1000],s[1000],f[1000],l;
bool pd()
{while (s[n+1]!=0){int k=n;while (s[n+1]!=0){s[n+1]--;s[k]--;if (s[k]<0) return 0;k--;}sort(s+1,s+n+2);}return 1;
}
int main()
{scanf("%d",&n);for (int i=1;i<=n+1;i++)scanf("%d",&a[i]);for (int i=1;i<=n+1;i++){if (f[a[i]]==1) {l++;b[l]=i;continue;}if (f[a[i]]==2) continue;for (int j=1;j<=n+1;j++)s[j]=a[j];s[i]=0;sort(s+1,s+n+2); if (pd()) {l++;f[a[i]]=1;b[l]=i;}elsef[a[i]]=0;}if (l!=0){printf("%d\n",l);for (int i=1;i<=l;i++)printf("%d\n",b[i]);}
}