http://acm.pku.edu.cn/JudgeOnline/problem?id=2356
discuss里说用鸽巢原理，我感觉我写出来的应该是o(n)，可是程序跑了500多
1
#include<stdio.h>
2#include<algorithm>
3using namespace std;
4#define Max_N 10000
5struct node{
6 int num;
7 int yu;
8};
9int N;
10int get[Max_N];
11struct node sum[Max_N];
12bool cmp(struct node a,struct node b)
13{
14 if(a.yu<b.yu)return true;
15 else if(a.yu==b.yu)return a.num<b.num;
16 else return false;
17}
18void solve()
19{
20 int i,j;
21 sum[0].yu=get[0]%N;
22 sum[0].num=0;
23 for(i=1;i<N;i++){
24 sum[i].yu=sum[i-1].yu+get[i];
25 sum[i].yu%=N;
26 sum[i].num=i;}//第一个数是get的第一个数，第二个数是前两个数的和取余，一共是N个数，就有N个和
27 //若其中一个和取余是0，显然成立，否则根据鸽巢原理，N个数占N-1个位子，显然会有一样的
28 sort(sum,sum+N,cmp);
29 if(!sum[0].yu){
30 printf("%d\n",sum[0].num+1);
31 for(i=0;i<=sum[0].num;i++)
32 printf("%d\n",get[i]);
33 return;
34 }
35 else {
36 for(i=0;i<N-1;i++)
37 if(sum[i].yu==sum[i+1].yu){
38 printf("%d\n",sum[i+1].num-sum[i].num);
39 for(j=sum[i].num+1;j<=sum[i+1].num;j++)
40 printf("%d\n",get[j]);
41 return;}
42
43 }
44 printf("0\n");
45}
46int main()
47{
48 int i;
49 while(scanf("%d",&N)!=EOF){
50 for(i=0;i<N;i++){
51 scanf("%d",&get[i]);
52 }
53 solve();}
54 return 0;
55}
以下是经过学习别人代码后重写的代码，0ms
1#include<iostream>
2using namespace std;
3#define Max_N 10001
4int main()
5{
6 int N,i,j;
7 int get[Max_N];
8 int sum[Max_N];
9 int b[Max_N];
10 sum[0]=0;
11 memset(b,0,sizeof(b));
12 scanf("%d",&N);
13 for(i=1;i<=N;i++){
14 scanf("%d",&get[i]);
15 if(!(get[i]%N)){
16 printf("1\n%d\n",get[i]);break;}
17 else {
18 sum[i]=(sum[i-1]+get[i])%N;
19 if(!sum[i]){
20 printf("%d\n",i);
21 for(j=1;j<=i;j++)
22 printf("%d\n",get[j]);
23 break;}
24 }
25 }
26 if(i>N){
27 for(i=1;i<=N;i++){
28 if(!b[sum[i]])
29 b[sum[i]]=i;
30 else{
31 printf("%d\n",i-b[sum[i]]);
32 for(j=b[sum[i]]+1;j<=i;j++)
33 printf("%d\n",get[j]);
34 break;}
35 }
36 }
37 return 0;
38}
posted on 2008-02-26 20:39
zoyi 阅读(218)
评论(0) 编辑 收藏 引用 所属分类:
acm