题目大意：输入一串数字，问你数字的组合方式，你可以随意用这些数字组合（无重复）来组合成一些整数（第一位不能为0），然后问你组合出来的整数的差最小是多少？
这一题可以用枚举的方法去做，这里我就用枚举和贪心（这个非常爽）的方法去。
首先这一题的限制是1000ms，我们知道全枚举的时间肯定是超时的，所以我们必须裁枝，我们这样看，我们得到的最小值，必须是两个数差别最小的时候才会出现，所以这里我们可以只用枚举lenth/2时候的数串的情况，这样就降低了很多的复杂度。
但是这样还是不够，但是我们知道，如果我们规定枚举的子串A一定比子串B大，则当枚举第一个的时候，如果枚举第二个的数的某个位（比如枚举012467,子串A为204,当子串B的百位枚举到7的时候）我们就可不必往十位和各位枚举了）这样也会缩减很多时间，还要把最高位是0的情况排除，这也是必须做的情况
当然，这一题还有一些很特殊的情况我们要考虑，比如当只输入01的时候，我们可能得不到结果，因为这个时候ans可能还是INF，这些情况要单独考虑
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; //全部用全局定义，防止递归太深产生MLE
static bool used_A[];
static bool used_B[];
static int input[];
static int zero_set[] = { , , , , , };//补0最多补5个
static int valueA, cutA, cutB, ans, length; void DFS_A(const int, const int);
void DFS_B(const int, const int); int main(void)//双DFS法
{
int case_sum;
char tmp;
while (~scanf("%d", &case_sum))
{
getchar();//消掉回车
for (int i = ; i < case_sum; i++)
{
length = ;
while ((tmp = getchar()) != '\n')
{
if (tmp != ' ')
input[length++] = tmp - '';
}
ans = INT_MAX;
cutA = length / ;//length要砍一半
cutA = cutA>length - cutA ? cutA : length - cutA;
cutB = length - cutA;
valueA = ; memset(used_A, , sizeof(used_A)); DFS_A(, );
if (ans != INT_MAX)
cout << ans << endl;
else//这个情况是针对x 0的情况的
cout << valueA << endl;
}
}
return ;
} void DFS_A(const int sumA, const int level)
{
//函数DFS_A，枚举数段A的所有可能，默认A的大小要比B的大
if (sumA == && level == )//出现第一位是0的情况，不用再枚举下去了
return;
if (level== cutA)
{
valueA = sumA;
memset(used_B, , sizeof(used_B));
DFS_B(, );
}
else if (level < cutA)
{
for (int i = ; i < length; i++)
{
if (!used_A[i])
{
used_A[i] = ;
DFS_A(sumA * + input[i], level + );
used_A[i] = ;//回溯
}
}
}
} void DFS_B(const int sumB, const int level)
{
//函数DFS_B，枚举数段B的所有可能，并对数值进行裁枝
if (sumB == && level == )//出现第一位是0的情况，不用再枚举下去了
return;
int tmp = sumB * zero_set[cutB - level];
if (tmp >= valueA)//默认A的大小要比B的大
return;
else if (cutB == level)
ans = min(ans, valueA - sumB);
else if (level < cutB)
{
for (int i = ; i < length; i++)
{
if (!used_A[i] && !used_B[i])
{
used_B[i] = ;
DFS_B(sumB * + input[i], level + );
used_B[i] = ;//回溯
}
}
}
}
但是这一份代码
在评测机跑了875MS，我不开心，怎么会那么慢？
其实一开始参考了这里http://blog.csdn.net/z309241990/article/details/19548297的方法，回过头来再看别人的判断条件
void DFS_B(const int sumB, const int level)
{
//函数DFS_B，枚举数段B的所有可能，并对数值进行裁枝
if (sumB == && level == )//出现第一位是0的情况，不用再枚举下去了
return;
int tmp = sumB * zero_set[cutB - level];
if (tmp >= valueA
&& (ans <= abs(valueA - tmp) && level > ))
return;
else if (cutB == level)
ans = min(ans, abs(valueA - sumB));
else if (level < cutB)
{
for (int i = ; i < length; i++)
{
if (!used_A[i] && !used_B[i])
{
used_B[i] = ;
DFS_B(sumB * + input[i], level + );
used_B[i] = ;//回溯
}
}
}
}
很好变成375MS，减了差不多一半
后来想了一下，我这个tmp>=valueA真是画蛇添足，根本就不需要，其实ans<=min(ans,abs(valueA-sumB))这个条件就已经排除了对称的情况了
比如如果一开始已经出了A：176和B：204的差值28，那么下一次A：204和B：167（注意我的顺序），就直接不用枚举176，可能你会问，不是还会有176的时候的更小的值吗？可是这个情况，绝对会被对称的情况优先排除，所以是不用考虑的
最后代码：
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; //全部用全局定义，防止递归太深产生MLE
static bool used_A[];
static bool used_B[];
static int input[];
static int zero_set[] = { , , , , , };//补0最多补5个
static int valueA, cutA, cutB, ans, length; void DFS_A(const int, const int);
void DFS_B(const int, const int); int main(void)//双DFS法
{
int case_sum;
char tmp;
while (~scanf("%d", &case_sum))
{
getchar();//消掉回车
for (int i = ; i < case_sum; i++)
{
length = ;
while ((tmp = getchar()) != '\n')
{
if (tmp != ' ')
input[length++] = tmp - '';
}
ans = INT_MAX;
cutA = length / ;//length要砍一半
cutB = length - cutA;
memset(used_A, , sizeof(used_A)); DFS_A(, );
if (ans != INT_MAX)
cout << ans << endl;
else//这个情况是针对x 0的情况的
cout << valueA << endl;
}
}
return ;
} void DFS_A(const int sumA, const int level)
{
//函数DFS_A，枚举数段A的所有可能，默认A的大小要比B的大
if (sumA == && level == )//出现第一位是0的情况，不用再枚举下去了
return;
if (level== cutA)
{
valueA = sumA;
memset(used_B, , sizeof(used_B));
DFS_B(, );
}
else if (level < cutA)
{
for (int i = ; i < length; i++)
{
if (!used_A[i])
{
used_A[i] = ;
DFS_A(sumA * + input[i], level + );
used_A[i] = ;//回溯
}
}
}
} void DFS_B(const int sumB, const int level)
{
//函数DFS_B，枚举数段B的所有可能，并对数值进行裁枝
if (sumB == && level == )//出现第一位是0的情况，不用再枚举下去了
return;
int tmp = sumB * zero_set[cutB - level];
if (ans <= abs(valueA - tmp) && level > )//如果补0以后大小都比ans大了，不用再搜了
return;
else if (cutB == level)
ans = min(ans, abs(valueA - sumB));
else if (level < cutB)
{
for (int i = ; i < length; i++)
{
if (!used_A[i] && !used_B[i])
{
used_B[i] = ;
DFS_B(sumB * + input[i], level + );
used_B[i] = ;//回溯
}
}
}
}
这个已经很快了
但是这个还可以用贪心去做，但是做起来异常复杂容易出错，不过我还是去做了这个异常复杂的贪心算法（其实也不算复杂），哈哈哈！
那怎么做呢？
主要思路就是，这个串是顺序的，如果是偶数，那么就找相邻差值最小的两个数（不包括0），假设两个子串的代表整数位n和m（n>m）那么这两个相邻第i+1个整数就作为n的最高位，i个整数作为m的最高位，然后从最小到大（包括0）填充n的剩余位置，从大到小填充m的剩余位置（如果存在两个相邻元素的差值相等，我们要把这些相邻元素都找出来并且做相同的步骤，最后比较得出的最小值）
如果是奇数，那么我们就把第一个不为0的数作为n的最高位，倒数最后一个数作为m的最高位，然后还是从小到大填充n的剩余位置，从大到小填充m的剩余位置（一定要注意千万不要数组越界，我就吃过这样的亏）
#include <iostream>
#include <functional>
#include <algorithm> using namespace std; static int input[];
static int length, cutA, cutB;
static int zero_set[] = { , , , , , }; int cal(const int, const int);
void cal_odd(const int, const int); int fcmop(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
} int main(void)
{
int case_sum, tmp; scanf("%d", &case_sum);
getchar();
for (int i = ; i < case_sum; i++)
{
length = ;
while ((tmp = getchar()) != '\n')
{
if (tmp != ' ')
input[length++] = tmp - '';
}
qsort(input, length, sizeof(int), fcmop);
cutA = length / ;
cutA = cutA > length - cutA ? cutA : length - cutA;
cutB = length - cutA;
if (length == )
cout << << endl;
else if (length == )
cout << input[] << endl;
else if (length == )
cout << abs(input[] - input[]) << endl;
else
{
int min_delta, min_sum;
if (input[] != )
{
if (cutA == cutB)//如果两个子串的长度相同，则取差值最小的相邻数，大的作为n的最高位，小的作为m的最高位，n的剩下位从小的补齐，m从大的补齐
{
min_sum = INT_MAX;
min_delta = input[] - input[];
for (int i = ; i < length - ; i++)
{
if (input[i + ] - input[i] < min_delta)
{
min_delta = input[i + ] - input[i];
min_sum = min(min_sum, cal(i + , i));
}
else if (input[i + ] - input[i] == min_delta)
min_sum = min(min_sum, cal(i + , i));
}
cout << min_sum << endl;
}
else cal_odd(, length - );
}
else//input[0]==0;
{
if (cutA == cutB)//如果字串长度相同，A-B则A的最高位要比B的最高位的差值要最小且比他大,且要从1开始
{
min_sum = INT_MAX;
min_delta = input[] - input[];
for (int i = ; i < length - ; i++)
{
if (input[i + ] - input[i] < min_delta)
{
min_delta = input[i + ] - input[i];
min_sum = min(min_sum, cal(i + , i));
}
else if (input[i + ] - input[i] == min_delta)
min_sum = min(min_sum, cal(i + , i));
}
cout << min_sum << endl;
}
else cal_odd(, length - );//如果cutA!=cutB,那么直接选一头一尾的最小
}
}
}
return ;
} int cal(const int posAS, const int posBS)
{
//专门算偶数重复的情况
int sumA = , sumB = , lenA = , lenB = ;
sumA = input[posAS]; sumB = input[posBS];
for (int i = ; lenA < cutA; i++)
{
if (i != posAS && i != posBS)
{
lenA++;
sumA = sumA * + input[i];
}
}
for (int i = length - ; lenB < cutB; i--)
{
if (i != posAS && i != posBS)
{
++lenB;
sumB = sumB * + input[i];
}
}
return sumA - sumB;
} void cal_odd(const int posAS, const int posBS)
{
int lenA = , lenB = , sumA = , sumB = ;
sumA = input[posAS]; sumB = input[posBS];
for (int i = ; lenA < cutA; i++)
{
if (i != posAS && i != posBS)
{
++lenA;
sumA = sumA * + input[i];
}
}
for (int i = length - ; lenB < cutB; i--)
{
if (i != posAS && i != posBS)
{
++lenB;
sumB = sumB * + input[i];
}
}
cout << sumA - sumB << endl;
}
最后最快的速度，32ms