3139784_re.cpp

部分PKU上的源码

#include<iostream.h>
int ok(int input[],int t,int result);
int pick(int input[],int t,int re);
int geshu=0;
void dubble(int a[],int t)
{int i,temp ,work;
for(int pass=1;pass<t;pass++)
{work=1;
 for(i=0;i<t-pass;i++)
	 if(a[i]>a[i+1]){temp=a[i];a[i]=a[i+1];a[i+1]=temp;work=0;}
	 if(work) break;
}
}
int main()
{int input[64],t=1,i,sum,result,re[64],k=0;
cin>>t;
while(t)
{sum=0;geshu=0;
for(i=0;i<t;i++){cin>>input[i];sum+=input[i];}
dubble(input,t);
result=input[t-1];
while(result<=sum/2)
{if(sum%result==0) {if(ok(input,t,result)) {re[k]=result;k++;result=sum;}} result ++;}
cin>>t;
}
for(i=0;i<k;i++){cout<<re[i]<<endl;}
return 1;
}



int ok(int input[],int t,int result)
{int j=t-1;
while(input[j]==result){input[j]=0;geshu++;j--;}
if(geshu==t) return 1;
while(geshu!=t)
{if(!pick(input,t,result)) return 0;}
return 1;
}


int pick(int input[],int t,int re)
{int i=0,j=t-1;
for(;i!=j;)
{if(input[j]==0) {j--;continue;}
if(input[i]==0) {i++;continue;}
if((input[i]+input[j])==re) {input[i]=0;input[j]=0;geshu+=2;return 1;}
if((input[i]+input[j])<re) {i++;continue;}
else {j--;continue;}}
i=0,j=t-1;
while(j)
{while(input[j]==0) j--;
 if(input[j]<re)break;
 else j--;}
if(j==0) return 0;
geshu ++;
while(j)
{if(pick(input,t,re-input[j])) return 1;j--;}
return 0;
}