题目大意：输入一串数字，问你数字的组合方式，你可以随意用这些数字组合（无重复）来组合成一些整数（第一位不能为0），然后问你组合出来的整数的差最小是多少？
这一题可以用枚举的方法去做，这里我就用枚举的方法去做吧。
首先这一题的限制是1000ms，我们知道全枚举的时间肯定是超时的，所以我们必须裁枝，我们这样看，我们得到的最小值，必须是两个数差别最小的时候才会出现，所以这里我们可以只用枚举lenth/2时候的数串的情况，这样就降低了很多的复杂度。
但是这样还是不够，但是我们知道，如果我们规定枚举的子串A一定比子串B大，则当枚举第一个的时候，如果枚举第二个的数的某个位（比如枚举012467,子串A为204,当子串B的百位枚举到7的时候）我们就可不必往十位和各位枚举了）这样也会缩减很多时间，还要把最高位是0的情况排除，这也是必须做的情况
当然，这一题还有一些很特殊的情况我们要考虑，比如当只输入01的时候，我们可能得不到结果，因为这个时候ans可能还是INF，这些情况要单独考虑
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 5 using namespace std; 6 7 //全部用全局定义，防止递归太深产生MLE 8 static bool used_A[10]; 9 static bool used_B[10]; 10 static int input[10]; 11 static int zero_set[6] = { 1, 10, 100, 1000, 10000, 100000 };//补0最多补5个 12 static int valueA, cutA, cutB, ans, length; 13 14 void DFS_A(const int, const int); 15 void DFS_B(const int, const int); 16 17 int main(void)//双DFS法 18 { 19 int case_sum; 20 char tmp; 21 while (~scanf("%d", &case_sum)) 22 { 23 getchar();//消掉回车 24 for (int i = 0; i < case_sum; i++) 25 { 26 length = 0; 27 while ((tmp = getchar()) != ‘\n‘) 28 { 29 if (tmp != ‘ ‘) 30 input[length++] = tmp - ‘0‘; 31 } 32 ans = INT_MAX; 33 cutA = length / 2;//length要砍一半 34 cutA = cutA>length - cutA ? cutA : length - cutA; 35 cutB = length - cutA; 36 valueA = 0; 37 38 memset(used_A, 0, sizeof(used_A)); 39 40 DFS_A(0, 0); 41 if (ans != INT_MAX) 42 cout << ans << endl; 43 else//这个情况是针对x 0的情况的 44 cout << valueA << endl; 45 } 46 } 47 return 0; 48 } 49 50 void DFS_A(const int sumA, const int level) 51 { 52 //函数DFS_A，枚举数段A的所有可能，默认A的大小要比B的大 53 if (sumA == 0 && level == 1)//出现第一位是0的情况，不用再枚举下去了 54 return; 55 if (level== cutA) 56 { 57 valueA = sumA; 58 memset(used_B, 0, sizeof(used_B)); 59 DFS_B(0, 0); 60 } 61 else if (level < cutA) 62 { 63 for (int i = 0; i < length; i++) 64 { 65 if (!used_A[i]) 66 { 67 used_A[i] = 1; 68 DFS_A(sumA * 10 + input[i], level + 1); 69 used_A[i] = 0;//回溯 70 } 71 } 72 } 73 } 74 75 void DFS_B(const int sumB, const int level) 76 { 77 //函数DFS_B，枚举数段B的所有可能，并对数值进行裁枝 78 if (sumB == 0 && level == 1)//出现第一位是0的情况，不用再枚举下去了 79 return; 80 int tmp = sumB * zero_set[cutB - level]; 81 if (tmp >= valueA)//默认A的大小要比B的大 82 return; 83 else if (cutB == level) 84 ans = min(ans, valueA - sumB); 85 else if (level < cutB) 86 { 87 for (int i = 0; i < length; i++) 88 { 89 if (!used_A[i] && !used_B[i]) 90 { 91 used_B[i] = 1; 92 DFS_B(sumB * 10 + input[i], level + 1); 93 used_B[i] = 0;//回溯 94 } 95 } 96 } 97 }
但是这一份代码
在评测机跑了875MS，我不开心，怎么会那么慢？
其实一开始参考了这里http://blog.csdn.net/z309241990/article/details/19548297的方法，回过头来再看别人的判断条件
1 void DFS_B(const int sumB, const int level) 2 { 3 //函数DFS_B，枚举数段B的所有可能，并对数值进行裁枝 4 if (sumB == 0 && level == 1)//出现第一位是0的情况，不用再枚举下去了 5 return; 6 int tmp = sumB * zero_set[cutB - level]; 7 if (tmp >= valueA 8 && (ans <= abs(valueA - tmp) && level > 0)) 9 return; 10 else if (cutB == level) 11 ans = min(ans, abs(valueA - sumB)); 12 else if (level < cutB) 13 { 14 for (int i = 0; i < length; i++) 15 { 16 if (!used_A[i] && !used_B[i]) 17 { 18 used_B[i] = 1; 19 DFS_B(sumB * 10 + input[i], level + 1); 20 used_B[i] = 0;//回溯 21 } 22 } 23 } 24 }
很好变成375MS，减了差不多一半
后来想了一下，我这个tmp>=valueA真是画蛇添足，根本就不需要，其实ans<=min(ans,abs(valueA-sumB))这个条件就已经排除了对称的情况了
比如如果一开始已经出了A：176和B：204的差值28，那么下一次A：204和B：167（注意我的顺序），就直接不用枚举176，可能你会问，不是还会有176的时候的更小的值吗？可是这个情况，绝对会被对称的情况优先排除，所以是不用考虑的
最后代码：
1 #include <iostream> 2 #include <functional> 3 #include <algorithm> 4 5 using namespace std; 6 7 //全部用全局定义，防止递归太深产生MLE 8 static bool used_A[10]; 9 static bool used_B[10]; 10 static int input[10]; 11 static int zero_set[6] = { 1, 10, 100, 1000, 10000, 100000 };//补0最多补5个 12 static int valueA, cutA, cutB, ans, length; 13 14 void DFS_A(const int, const int); 15 void DFS_B(const int, const int); 16 17 int main(void)//双DFS法 18 { 19 int case_sum; 20 char tmp; 21 while (~scanf("%d", &case_sum)) 22 { 23 getchar();//消掉回车 24 for (int i = 0; i < case_sum; i++) 25 { 26 length = 0; 27 while ((tmp = getchar()) != ‘\n‘) 28 { 29 if (tmp != ‘ ‘) 30 input[length++] = tmp - ‘0‘; 31 } 32 ans = INT_MAX; 33 cutA = length / 2;//length要砍一半 34 cutB = length - cutA; 35 memset(used_A, 0, sizeof(used_A)); 36 37 DFS_A(0, 0); 38 if (ans != INT_MAX) 39 cout << ans << endl; 40 else//这个情况是针对x 0的情况的 41 cout << valueA << endl; 42 } 43 } 44 return 0; 45 } 46 47 void DFS_A(const int sumA, const int level) 48 { 49 //函数DFS_A，枚举数段A的所有可能，默认A的大小要比B的大 50 if (sumA == 0 && level == 1)//出现第一位是0的情况，不用再枚举下去了 51 return; 52 if (level== cutA) 53 { 54 valueA = sumA; 55 memset(used_B, 0, sizeof(used_B)); 56 DFS_B(0, 0); 57 } 58 else if (level < cutA) 59 { 60 for (int i = 0; i < length; i++) 61 { 62 if (!used_A[i]) 63 { 64 used_A[i] = 1; 65 DFS_A(sumA * 10 + input[i], level + 1); 66 used_A[i] = 0;//回溯 67 } 68 } 69 } 70 } 71 72 void DFS_B(const int sumB, const int level) 73 { 74 //函数DFS_B，枚举数段B的所有可能，并对数值进行裁枝 75 if (sumB == 0 && level == 1)//出现第一位是0的情况，不用再枚举下去了 76 return; 77 int tmp = sumB * zero_set[cutB - level]; 78 if (ans <= abs(valueA - tmp) && level > 0)//如果补0以后大小都比ans大了，不用再搜了 79 return; 80 else if (cutB == level) 81 ans = min(ans, abs(valueA - sumB)); 82 else if (level < cutB) 83 { 84 for (int i = 0; i < length; i++) 85 { 86 if (!used_A[i] && !used_B[i]) 87 { 88 used_B[i] = 1; 89 DFS_B(sumB * 10 + input[i], level + 1); 90 used_B[i] = 0;//回溯 91 } 92 } 93 } 94 }
这个已经很快了
但是这个还可以用贪心去做，可以是0ms，的确非常快，但是做起来异常复杂容易出错。
Enum:Smallest Difference(POJ 2718)
原文：http://www.cnblogs.com/Philip-Tell-Truth/p/4853362.html