题意:给定一组数字,如0, 1, 2, 4, 6, 7,用这些数字组成两个数,并使这两个数之差最小。求这个最小差。在这个例子上,就是204和176,差为28。
分析:首先可以想到,这两个数必定是用各一半数量的数字组成的数,如给出6个数,把这6个数分为两组,每组3个,这样组成的数字的差必定比其他方式小。接下来的任务就是穷举所有可能出现的组合,并求出最小差。在这里可以使用STL的next_permutation函数来求给定这组数字的所有排列,并将其分为两组组成数字,然后记录最小差。需要注意第一个数位不能为0。
/*
input:
1
0 1 2 4 6 7
output:
28
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib> using namespace std; const int INF = ; //输入
int n;
int a[]; int num(int i, int j){
//从数组恢复数字
int x = ;
for(int k = i; k < j; k ++){
x *= ;
x += a[k];
}
return x;
} void solve(){
//初始化
int ans = INF; //结果
int k = n / ; //从n个数中挑出n/2个
do{
if(a[] == || a[k] == )continue; int x = num(, k), y = num(k, n);
ans = min(ans, abs(x - y));
}while(next_permutation(a, a + n));
//特判包含0的两元素数组
if(n == )
ans = abs(a[] - a[]);
printf("%d\n", ans);
} int main(int argc, char const *argv[]){ int T;
scanf("%d", &T);
getchar();
while(T --){
char c;
n = ;
while((c = getchar()) != '\n'){
if(c != ' '){
a[n ++] = c - '';
}
}
solve();
} return ;
}