题意
给你一个0-9的串，挑其中一部分的数字排列成一个数，其它数字排列成一个数（两个数都不能有前导0）问你这两个数差的绝对值最小是多少
思路
n很小，2-10，数字不会重复出现，直接暴力枚举即可注意，不能复杂度过高，稍微有些技巧的就是两个数的位数应该尽可能接近，即都是n/2最好所以枚举全排列，计算下在n/2的位置前后两个数差是几即可
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
const int maxn =
12;
const int inf =
0x3f3f3f3f;
int a[maxn];
int n;
int ans = inf;
int cal(
int inx){
int num1 =
0, num2 =
0;
for (
int i=
0;i<inx;i++){
num1 *=
10;
num1 += a[i];
}
for (
int i=inx; i < n; i++){
num2 *=
10;
num2 += a[i];
}
return abs(num1 - num2);
}
void dfs(
int dep){
if (dep == n){
if (n >
3 && a[
0] ==
0){
return;
}
int index = n /
2;
if (n >=
3 && a[index] ==
0){
return;
}
ans = min(cal(index), ans);
return;
}
for (
int i=dep;i<n;i++){
swap(a[i], a[dep]);
dfs(dep +
1);
swap(a[dep], a[i]);
}
}
int main(){
int T;
char str[
30];
cin>>T;
cin.getline(str,
1);
while(T--){
ans = inf;
string s;
cin.getline(str,
30);
s = str;
n = s.length() /
2 +
1;
for (
int i=
0;i<s.length();i+=
2){
a[i/
2] =
int(s[i] -
'0');
}
dfs(
0);
cout << ans << endl;
}
return 0;
}
