| ||||||||||
| 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: |