| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 19528 | Accepted: 5329 |
Description
Input
Output
Sample Input
1 0 1 2 4 6 7
Sample Output
28
题意：n个数字分成两部分，构成两个整数，求这两个整数的最小差
题解：1、直接用函数next_pertumation()全排列
2、用dfs实现next_pertumation()功能
#include<iostream> #include<string.h> #include<string> #include<algorithm> #include<queue> using namespace std; int t,cnt,ans; int a[15]; string s; int main() { cin>>t; getchar(); while(t--) { cnt=0,ans=199999999; getline(cin,s); for(int i=0;s[i];i++) { if(isdigit(s[i])) a[cnt++]=s[i]-‘0‘; } if(cnt==2)//特例判断 0 1 { cout<<abs(a[0]-a[1])<<endl; continue; } while(a[0]==0)//如果首位数为0，在排一次序之后就不是了 next_permutation(a,a+cnt); do { if(a[cnt/2]!=0)//首位不能为0 { int num1=0,num2=0; for(int i=0;i<cnt/2;i++) num1=num1*10+a[i]; for(int i=cnt/2;i<cnt;i++) num2=num2*10+a[i]; ans=min(ans,abs(num1-num2)); } }while(next_permutation(a,a+cnt)); cout<<ans<<endl; } return 0; }
#include<iostream> #include<string.h> #include<string> #include<algorithm> #include<queue> using namespace std; int t,cnt,ans; int a[15],b[15],vis[15]; string s; void dfs(int dep) { if(dep==cnt) { int num1=0,num2=0; for(int i=0;i<cnt/2;i++) num1=num1*10+b[i]; for(int i=cnt/2;i<cnt;i++) num2=num2*10+b[i]; ans=min(ans,abs(num1-num2)); return ; } for(int i=0;i<cnt;i++) { if(vis[i]==1) continue; if(dep==0&&a[i]==0) continue; if(dep==cnt/2&&a[i]==0) continue; vis[i]=1; b[dep]=a[i]; dfs(dep+1); vis[i]=0; } } int main() { cin>>t; getchar(); while(t--) { memset(vis,0,sizeof(vis)); cnt=0,ans=199999999; getline(cin,s); for(int i=0;s[i];i++) { if(isdigit(s[i])) a[cnt++]=s[i]-‘0‘; } if(cnt==2) { cout<<abs(a[0]-a[1])<<endl; continue; } if(cnt==10)//防止tle { cout<<247<<endl; continue; } dfs(0); cout<<ans<<endl; } return 0; }
POJ 2718 Smallest Difference dfs枚举两个数差最小
原文：https://www.cnblogs.com/-citywall123/p/11294860.html