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:大侠们! 指导一下小弟吧!我用的算法依然是排序加回溯,但都超时了N次了。(附上程序)In Reply To:大侠们! 指导一下小弟吧!我用的算法依然是排序加回溯,但都超时了N次了。(附上程序) Posted by:team7 at 2005-11-03 21:41:54 > #include "stdio.h" > #include "stdlib.h“ > > void bol(int a[],int T) > { > int i,j,change,t; > for(i=T-1,change=1;i>=1&&change;i--) > { > change=0; > for(j=0;j<i;j++) > { > if(a[j]<a[j+1]) > { > t=a[j]; > a[j]=a[j+1]; > a[j+1]=t; > change=1; > } > } > } > } > > int T; > int huisu(int k,int b[],int a[]); > > int main() > { > int i,k,b[70]; > int num,a[70],sum,n,n2; > scanf("%d",&T); > while(T) > { > num=0; > sum=0; > n2=0; > for(i=0;i<T;i++) > { > scanf("%d",&a[i]); > if(a[i]>50) {a[i]=0;n2++;} > sum+=a[i]; > } > bol(a,T); > > if(a[0]==0) {printf("0\n");continue;} > k=sum/a[0]; > printf("%d\n",a[0]); > for(;k>=1;k--) > { > if(sum%k==0) > { > n=sum/k; > if(a[k]+a[k-1]>n) continue; > for(i=0;i<k;i++) > { > b[i]=n; > > } > num=huisu(k,b,a); > } > if(num==1) break; > } > printf("%d\n",sum/k); > > scanf("%d",&T); > } > return 0; > } > > int huisu(int k,int b[],int a[]) > { > int i,j; > int n,m,num; > int flag; > n=0; > m=0; > > for(i=0;i<k;i++) > { > > if(b[i]!=0) > { > for(j=0;j<T;j++) > { > > flag=0; > if(a[j]==m) continue; > > if(a[j]!=0&&a[j]<=b[i]) > { > > n=b[i]; > flag=1; > b[i]=b[i]-a[j]; > m=a[j]; > a[j]=0; > if(i==(k-1)&&b[i]==0) > return 1; > else > num=huisu(k,b,a); > } > if(flag==1) > { > if(num==1) return 1; > else {b[i]=n;a[j]=m;} > } > > } > if(b[i]!=0) return 0; > } > } > return 0; > } 你是WA,必须用回溯吗?请问先排序,再从大到小拼,为什么不行呢? 1 1 1 2 2 2 5 5 5 就从5开始,前三个可以,6-5-1, 6-5-1, 6-5-1 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator