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:Re:这题也可以爆搜的 Posted by:vjudge110 at 2016-03-05 23:00:52 你们爆搜水过 我10!的复杂度爆搜竟然超时。。。。 #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <cmath> using namespace std; int minn=999999999; int m; char a[11]={0}; char perm1[11]={0},perm2[11]={0}; int powa(int i,int j) { int powar=i; if(j>0) { for(int k=1;k<=j-1;k++) { powar*=i; } return powar; } else if(j==0) { powar=1; return powar; } } int sum(char perm[]) { int len=strlen(perm); int num=0; int jlen=len; while(jlen>=1) { for(int i=0;i<len;i++) { int t=jlen-1; num+=(perm[i]-'0')*powa(10,t); jlen--; } } return num; } int main() { //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); scanf("%d\n",&m); char ch; for(int i=0;i<m;i++) { minn=99999999; int k; int tag=0; while((ch=getchar())!='\n') { if(ch!=' ') { a[tag]=ch; tag++; } } int len=strlen(a); do { int flag=0; if(len%2==1) { for(k=0;k<len/2+1;k++) { perm1[k]=a[k]; } for(int j=k;j<len;j++) { perm2[flag]=a[j]; flag++; } if(perm1[0]!='0' && perm2[0]!='0') { int tag1=sum(perm1); int tag2=sum(perm2); int del=abs(tag1-tag2); if(minn>del) { minn=del; } } } else if(len%2==0) { for(k=0;k<len/2;k++) { perm1[k]=a[k]; } for(int j=k;j<len;j++) { perm2[flag]=a[j]; flag++; } if(perm1[0]!='0' && perm2[0]!='0' && perm2[0]-perm1[0]==1) { int tag1=sum(perm1); int tag2=sum(perm2); int del=abs(tag1-tag2); if(minn>del) { minn=del; } } } }while(next_permutation(a,a+len)); printf("%d\n",minn); } return 0; } 正在优化。。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator