Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:我的一直循环下去了In Reply To:对没AC的同学一点提示 Posted by:PlayerZ at 2008-08-07 08:58:43 我的程序对其他数据都是瞬间出结果,但你这个就好像死循环了,不过也找不到错误啊? 还有,好像很多通过了的程序也很慢才能出结果或者也死了。 #include <stdio.h> #include <iostream> using namespace std; int a[65],stack[65],used[65],poped; int main() { // freopen("in.txt","r",stdin); int i,j,k,n,max,sum,temp,div,stacklen; while( scanf("%d",&n) && n ) { sum=max=0; for(i=0;i<n;++i) { scanf("%d",&a[i]); sum+=a[i]; if(max<a[i]) max=a[i]; // 输入木棍的最大值。 } for(i=0;i<n-1;) // 冒泡排序,从大到小排列木棍。 { k=n; for(j=n-1; j>i; --j) if(a[j]>a[j-1]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; k=j; } i=k; } // for(i=0;i<n;++i) cout<<a[i]<<" "; // cout<<endl; i=max; // 从木棍最大长度开始搜索。 // cout<<"max= "<<max<<" sum="<<sum<<endl; // long xx=1; while(1) // 搜索。 { while(sum%i) ++i; // 结果长度 肯定能整除总长度 // cout<<"\n ****** i= "<<i<<" n="<<n<<endl; if(i==sum) break; memset(stack,0,sizeof(stack)); memset(used,0,sizeof(used)); stack[1]=0; stacklen=1; used[0]=1; div=a[stack[stacklen]]; // div: 当前搜索的一段木棍的总长度。 j=0; poped=-1; int flag=0; while(stacklen>0 && stacklen<n) { ++j; // ++xx; // if(xx==500) // break; // cout<<"stacklen="<<stacklen<<" j="<<j<<endl; // int xy=0; // for(k=1;k<=stacklen;++k) // { printf("stack[%d]= %d\t",k,a[stack[k]]); xy+=a[stack[k]]; } // cout<<"\ni="<<i<<" sum="<<sum<<" all stack="<<xy<<"\t"; // cout<<endl<<"div="<<div<<" poped="<<poped<<endl; while( div<i && j<n) { if(used[j]==0 && div+a[j]<=i && a[j]!=poped) { div+=a[j]; used[j]=1; ++stacklen; stack[stacklen]=j; } ++j; // cout<<"###### div="<<div<<endl; } poped=-1; if(div==i) { j=1; while(used[j]==1) ++j; div=0; --j; } else { j=stack[stacklen]; poped=a[j]; --stacklen; used[j]=0; if(div-a[j]<0) div=i; div-=a[j]; if(div==0 && j>n/5) // 这个判断就是专们为你的数据设计的, { // 有他能过你的数据,但其他数据可能过不了了。 flag=j-1; while(used[flag]==1 && flag>0) --flag; if(flag==0) break; } } } // cout<<endl; if(stacklen==n) break; ++i; } cout<<i<<endl; } return 0; } Followed by: Post your reply here: |