Smallest Difference
Given a number of distinct decimal digits, you can form one integer by choosing a non-empty subset of these digits and writing them in some order. The remaining digits can be written down in some order to form a second integer. Unless the resulting integer is 0, the integer may not start with the digit 0.
For example, if you are given the digits 0, 1, 2, 4, 6 and 7, you can write the pair of integers 10 and 2467. Of course, there are many ways to form such pairs of integers: 210 and 764, 204 and 176, etc. The absolute value of the difference between the integers in the last pair is 28, and it turns out that no other pair formed by the rules above can achieve a smaller difference.
Input
The first line of input contains the number of cases to follow. For each case, there is one line of input containing at least two but no more than 10 decimal digits. (The decimal digits are 0, 1, ..., 9.) No digit appears more than once in one line of the input. The digits will appear in increasing order, separated by exactly one blank space.
Output
For each test case, write on a single line the smallest absolute difference of two integers that can be written from the given digits as described by the rules above.
Sample Input
1
0 1 2 4 6 7
Sample Output
28 我们看到这道题有没有想到将这些数进行全排列？然后从中间剪开拼成两个数？？没错，这就是正解！我们在读入的时候将这串数长度存为n,同时思考的时候就要想到要让两数差最小就要将他们位数尽量相同，也就是,它们位数尽量接近，不妨让a为较大数，b为较小数，那么就进行分类讨论：当n为偶数时令a位数为n/2，b位数也为n/2，当n为偶数时令a位数为n/2+1，b位数为n/2,
C++版本一
调用全排列函数。
相信很多人第一眼看到这一题就想到了算法函数库(algorithm)中的next_permutation()函数，它的函数作用是将数组中从第i个数至第j个数进行全排列。对于这道题正好，你将它排列出的数进行分割，还要让首位不为 0，枚举所有的数后相减取其中最小值就可以了。这是最好写的一种。代码如下：
#include<deque>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define INF int(1e9)//1e9=1000000000
using namespace std;
int read()//请忽视(这是读入优化)
{
int f=1,x=0;
char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
return f*x;
}
int num[11];//这是用来存读入的数字的
int main()
{
char c;
int t,n=0,ans,tot=0,a,b;
scanf("%d",&t);
while(t!=0)
{
n=0;
ans=INF;//注意存答案的变量要赋极大值
while(1)//这一段就是前面的'伪'读入优化
{
scanf("%c",&c);
if(c==' ')continue;
if(c=='\n')break;
num[++n]=c-'0';
}
if(n==2)//自己写的next_permutation貌似不能处理长度为二的数列，于是特判
{
t--;
printf("%d\n",num[2]-num[1]);
continue;
}
while(next_permutation(num+1,num+n+1))//进行这些数字的全排列
{
if(num[1]!=0&&num[n/2+1]!=0)//判断数字首位不能为0
{
a=b=0;
for(int i=1;i<=n/2;i++)//分割数
a=a*10+num[i];
for(int j=n/2+1;j<=n;j++)//分割数
b=b*10+num[j];
tot=a-b;
if(tot<0) tot=-tot;//取绝对值
if(tot<ans) ans=tot;//给存答案的变量更新
}
}
printf("%d\n",ans);
t--;
}
return 0;
}
C++版本二
手写全排列(DFS)
用简单的搜索来做肯定要超时，如果你的代码和下面的差不多，那你这题就TLE(超时)了：
#include<deque>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[11];
bool flag[11];
void DFS(int x)//枚举当前第几位
{
if(x>n) //输出方案
{
printf("%d",a[1]);
for(int i=2;i<=n;i++)
printf(" %d",a[i]);
printf("\n");
return;
}
for(int i=1;i<=n;i++)
if(flag[i]==0)//若这i个数没被用过
{
a[x]=i;
flag[i]=1;//标记
DFS(x+1);
flag[i]=0;//标记清零
}
return ;
}
int main()
{
scanf("%d",&n);
DFS(1);
return 0;
}
所以我们要优化！！！我们可以用一种类似于选择排序的思想，交换第i个数和第j个数,然后进入递归再交换，代码如下：
#include<deque>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define INF int(1e9)//1e9=1000000000
int read()
{
int f=1,x=0;
char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
return f*x;
}
int num[11],ans,n;
void dfs(int i)
{
if(i>n)
{
if(num[1]!=0&&num[n/2+1]!=0)//仍然判断数字首位不为零
{
int a=0,b=0,tot;
for(int i=1;i<=n/2;i++)
a=a*10+num[i];
for(int j=n/2+1;j<=n;j++)
b=b*10+num[j];
tot=a-b;
if(tot<0) tot=-tot;//取绝对值
if(tot<ans) ans=tot;
}
return ;
}
for(int j=i;j<=n;j++)
{
swap(num[i],num[j]);//交换两数再进行判断
dfs(i+1);
swap(num[i],num[j]);//交换回来
}
return ;
}
int main()
{
int t=read();
char c;
while(t!=0)
{
n=0;
ans=INF;
while(1)
{
scanf("%c",&c);
if(c==' ')continue;
if(c=='\n')break;
num[++n]=c-'0';
}
if(n==2)
{
t--;
printf("%d\n",num[2]-num[1]);
continue;
}
dfs(1);
printf("%d\n",ans);
t--;
}
return 0;
}
C++版本三
通过贪心找最佳方案。
1.如果n为奇数。
这说明之前所设的a必定为较大数，那我们就要让大的数尽量小，小的数尽量大，才能使他们差值最小。于是我们要把最小的一个非零数字给a,如果有零，那作为a的第二位，然后将所剩的数从小到大填入a，直到a的位数达到n/2+1,然后再将剩下的数从大到小给b，那么这样a,b两数差之必然最小。
2.如果n为偶数。
还是设a为较大数，两个位数相等的数他们首位越接近，差就越小于是我们要把所有首位非零的数枚举一遍，找出差值最小的多组数分别作为a,b的首位。还是将较大的数给a，较小的数给b,然后处理方法就和之前的处理方法一样，还是大的数尽量小，小的数尽量大，才能使他们差值最小。如果有零，那作为a的第二位，然后将所剩的数从小到大填入a，直到a的位数达到n/2+1,然后再将剩下的数从大到小给b，那么这样a,b两数差之必然最小(我不会告诉你我写的后面我是复制前面的~~),代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<deque>
#define INF int(1e9)
using namespace std;
int read()
{
int f=1,x=0;
char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
return f*x;
}
int num[11],ans,n,minvalue[11];//minvalue存的有最小差值为mintot的相邻两数
int main()
{
int t=read(),a,b,mintot,mint;//有最小差值为mintot的相邻两数有mint对
char c;
while(t!=0)
{
mintot=10;//mintot最多也就等于8对
mint=a=b=n=0;//a较大数b较小数
ans=INF;
while(1)
{
scanf("%c",&c);
if(c==' ')continue;
if(c=='\n')break;
num[++n]=c-'0';
}
if(n==2)
{
t--;
printf("%d\n",num[2]-num[1]);
continue;
}
else if(n%2!=0)//如果n为奇数，对照前面情况1
{
if(num[1]==0)//处理首位为零的情况
{
a=num[2]*10;
for(int i=3;i<=(n+1)/2;i++)
a=a*10+num[i];
}
else//首位不为零
{
for(int i=1;i<=(n+1)/2;i++)
a=a*10+num[i];
}
for(int i=n;i>=(n+1)/2+1;i--)
b=b*10+num[i];
ans=a-b;
}
else //如果n为偶数，对照前面情况2
{
for(int i=2;i<=n;i++)//找最小差值为mintot的相邻两数有几对
{
if(num[i]-num[i-1]<mintot&&num[i-1]!=0)//一定要首位不为零
{
mintot=num[i]-num[i-1];
mint=1;
minvalue[mint]=i;
}
else if(num[i]-num[i-1]==mintot&&num[i-1]!=0)
minvalue[++mint]=i;
}
for(int i=1;i<=mint;i++)//分别尝试这最小差值为mintot的相邻两数
{
a=num[minvalue[i]];
b=num[minvalue[i]-1];
int j=1,t=0;
while(t<n/2-1)
{
if(j!=minvalue[i]&&j!=minvalue[i]-1)
{
a=a*10+num[j];
t++;
}
j++;
}
j=n,t=0;
while(t<n/2-1)
{
if(j!=minvalue[i]&&j!=minvalue[i]-1)
{
b=b*10+num[j];
t++;
}
j--;
}
if(a-b<ans)
ans=a-b;
}
}
printf("%d\n",ans);
t--;
}
return 0;
}
C++版本四
用的双重DFS做的，速度还比较快，其中有一个很重要的剪枝，若当前搜索的第二个数后面全部补零与第一个数所产生的差值比当前所搜索到的结果还要大，那么就直接返回。这个剪枝就是超时与几十MS的差距
注意一点就是可能有0 与一个数字存在的情况，比如0 3,0 5等等。
其他的就比较简单了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
const int inf=1<<29;
int num[20],cnt,cnta,cntb,val,ans;
int nums[10]={1,10,100,1000,10000,100000,1000000};
bool usea[20],useb[20];
char ch;
void DFS_B(int vals,int deep)
{
if(deep>0&&abs(val-vals*nums[cntb-deep])>=ans)
return;
if(deep==cntb)
{
ans=min(ans,max(val,vals)-min(val,vals));
return;
}
for(int i=0;i<cnt;i++)
if(!usea[i]&&!useb[i])
{
if(deep==0&&num[i]==0)
continue;
useb[i]=1;
DFS_B(vals*10+num[i],deep+1);
useb[i]=0;
}
}
void DFS_A(int vals,int deep)
{
if(deep==cnta)
{
val=vals;
memset(useb,0,sizeof(useb));
DFS_B(0,0);
return;
}
for(int i=0;i<cnt;i++)
if(!usea[i])
{
if(deep==0&&num[i]==0)
continue;
usea[i]=1;
DFS_A(vals*10+num[i],deep+1);
usea[i]=0;
}
}
int main()
{
int T;
while(scanf("%d",&T)!=EOF)
{
getchar();
while(T--)
{
cnt=0;
while((ch=getchar())!='\n')
{
if(ch>='0'&&ch<='9')
num[cnt++]=ch-'0';
}
cnta=cnt>>1;
cntb=cnt-cnta;
ans=inf;
DFS_A(0,0);
if(ans==inf)
printf("%d\n",val);
else
printf("%d\n",ans);
}
}
return 0;
}
C++版本五
题解：给一串0到9的数，选择几个组成num1，剩下的组成num2，问最小的差值，当有两个数字时不能0开始；暴力，先选数字然后全排列
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int ans;
int vis[10];
int p[10] = {0,1,10,100,1000,10000,100000,1000000,10000000,100000000};
int get(int* a){
int i = 0;
while(1){
char c = getchar();
if(c == ' ')continue;
if(c == '\n')return i;
a[i ++] = c - '0';
vis[c - '0'] = 1;
}
}
int cal(int *a, int n){
int x = 0;
for(int i = 0; i < n; i++){
// printf("%d ", a[i]);
x = x * 10 + a[i];
}//printf("\n计算的结果是：\n", x);
return x;
}
void distribute(int* a, int an, int* l, int ln, int* r, int rn, int i){
if(i == an){
// puts("l的元素是：");
// for(int j = 0; j < ln; j++){
// printf("%d ", l[j]);
// }puts("");
//
// puts("r的元素是：");
// for(int j = 0; j < rn; j++){
// printf("%d ", r[j]);
// }puts("");
if(ln == 0 || rn == 0){
return;
}
if(abs(rn - ln) > 1){
return;
}
do{
do{
if(ln > 1 && l[0] == 0){
continue;
}
if(rn > 1 && r[0] == 0){
continue;
}
int x = cal(l, ln);
int y = cal(r, rn);
// printf("x = %d\ny = %d\n", x, y);
if(abs(x - y) <= ans){
ans = abs(x - y);
}
}while(next_permutation(r, r + rn));
}while(next_permutation(l, l + ln));
return;
}
l[ln] = a[i];
distribute(a, an, l, ln + 1, r, rn, i + 1);
r[rn] = a[i];
distribute(a, an, l, ln, r, rn + 1, i + 1);
}
int main(){
int T;
scanf("%d", &T);
getchar();
int a[10], l[10], r[10];
while(T--){
memset(vis, 0, sizeof(vis));
int n = get(a);
ans = 0x3f3f3f3f;
// if(n == 10){
// puts("247");
// continue;
// }else if(n == 9){
// int m[10] = {2469,10469,469,369,359,358,359,369,469,1469};
// for(int i = 0; i < 10; i++){
// if(!vis[i]){
// printf("%d\n", m[i]);
// }
// }
// continue;
// }
distribute(a, n, l, 0, r, 0, 0);
printf("%d\n", ans);
}
return 0;
} C++版本六
将一个数分成两个数，这两个数的数字顺序可以任意变化，不能有前导0，求这两个数差值的最小值。
显然有n个数，要使差值最小，必然一个数长n/2，一个数长n-n/2.
可以利用二进制枚举(bitset！！！)，把一个数切割成两个整数，注意有些情况要舍去(长度不是n/2的，前导为0但不是一位数的)。
这时候已经切割好s1和s2.然后对这两个数进行全排列，就可以的得到所有情况，比较取最小值即可。
学到了好多关于STL的东西……
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include<cmath>
#include<bitset>
using namespace std;
int main()
{
int n;
cin>>n;
cin.ignore();
while(n--){
string all;
getline(cin,all);
all.erase(remove(all.begin(),all.end(),' '),all.end());//删除空格
int length=all.size();
int cut=length/2;
int permute=1<<length;
int result=0x7fffffff;
do{
bitset<10> used=static_cast<bitset<10> >(permute);
string s1,s2;
for(int i=0;i<length;i++){
if(used[i]){
s1+=all[i];
}
else{
s2+=all[i];
}
}
if(s1.size()!=cut){
continue;
}
if(s1[0]=='0'&&s1.size()>1){
continue;
}
//s1,s2已经枚举出来了
//穷举它们
do{
int n1=atoi(s1.c_str());//将字符串转化成整数
do{
if(s2[0]=='0'&&s2.size()>1){
continue;
}
int n2=atoi(s2.c_str());//将字符串转化成整数
int dif=abs(n1-n2);
//cout<<s1<<" "<<s2<<"dif:"<<dif<<"result:"<<result<<endl;
result=min(dif,result);
}while(next_permutation(s2.begin(),s2.end()));//全排列
}while(next_permutation(s1.begin(),s1.end()));
}while(--permute);
cout<<result<<endl;
}
return 0;
}
C++版本七
暴力搜索OLE万岁
参考无数博客剪枝以后
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>
using namespace std;
const int inf=60;
int t;
int ans;
int a[11];
//int b[11];
int vis[11];
int c;
int flag=0;
int nums[10]={1,10,100,1000,10000,100000,1000000};
void dfs2(){
int num1,num2;
for(int i=c/2;i<c/2+1;i++){
if((i!=1&&a[0]==0)||(i!=c&&a[i]==0)) continue;
num1=a[0];
for(int j=1;j<i;j++)
{
num1=num1*10+a[j];
}
//cout << num1<<endl;
num2=a[i];
for(int k=i+1;k<c;k++)
{
num2=num2*10+a[k];
}
int t=abs(num1-num2);
//cout << num2<<endl;
//cout << t<<endl;
if(!flag) {
ans=t;
flag=1;
}
if(ans>t&&flag) ans=t;
//ans=min(ans,t);
}
}
//全排列
void dfs(int k){
if(k==c){
dfs2();
//for(int i=0;i<c;i++)
// printf("\n");
return;
}
for(int j=k;j<c;j++)
{
swap(a[k],a[j]);//交换两数再进行判断
dfs(k+1);
swap(a[k],a[j]);//交换回来
}
// for(int i=0;i<c;i++){
// if(vis[i]==0){
// if(k==0&&a[i]==0)
// continue;
// vis[i]=1;
//
// dfs(vals*10+a[i],k+1);
// vis[i]=0;
// }
// }
}
int main()
{
scanf("%d",&t);
getchar();
while(t--){
c=0;
flag=0;
char temp;
while((temp=getchar())!='\n'){
if(temp>='0'&&temp<='9')
{
a[c++]=temp-'0';
}
}
//printf("%d",c);
memset(vis,0,sizeof(vis));
dfs(0);
printf("%d\n",ans);
}
//cout << "Hello world!" << endl;
return 0;
}
CVTE公司福利 270人发布
