1 0 1 2 4 6 7
28
拿到题目，差分数字，列出所有的可能性，然后做差，取最小。但是，盲目暴力是肯定TLE的，所以考虑每种区分和排列，如果两组位数相差大，肯定没有两组位数一样的差小。所以，我们可以列除所有的排列，然后取前一半和后一半，就算是奇数相差一位也比差2位以上要小。自于全排列，我们用next_permutation()来玩，这玩意还挺智能的，迭代器也能使。
对整个数组全排列，在均分，前一半一个，后一半一个，这样可以使得所有情况都能遍历到（因为全排列本身在前半段后者后半段所有数字的组合都能出现，而且会进行排列）。
AC代码很短（借鉴了网上CSDNAC_hell的代码）：
#include <stdio.h> #include <iostream> #include <algorithm> #include <vector> #include <stdlib.h> using namespace std; int n1, n2;//分成两段算出的值 vector<int> a;//记录一开始的数组 string s; int mindif;//最小差值 int main(void) { int n; cin >> n; cin.get(); for(int i = 0; i < n; i++) { a.clear(); mindif = 0x3fffffff; getline(cin, s); int sub = 0; for(int j = 0; j < s.size(); j++) { int t = 0; while(j < s.size() && s[j] != ‘ ‘) { t *= 10; t += s[j] - ‘0‘; j++; } a.push_back(t); } if(a.size() == 2)//2个要特判，因为1/2==0 mindif = abs(a[0] - a[1]);
else { do //do while,因为采用全排列函数的话就变成下一个升序的排列了 { n1 = n2 = 0; if(!a[0] || !a[a.size() / 2]) continue; for(int i = 0; i < a.size() / 2; i++) { n1 *= 10; n1 += a[i]; } for(int i = a.size() / 2; i < a.size(); i++) { n2 *= 10; n2 += a[i]; } mindif = min(mindif, abs(n1 - n2)); }while(next_permutation(a.begin(), a.end())); } printf("%d\n", mindif); } return 0; }
挑战程序设计竞赛2.1习题：Smallest Difference POJ - 2718
原文：https://www.cnblogs.com/jacobfun/p/12197309.html