POJ 2718 Smallest Difference：全排列枚舉最小差值

題目大意

給定 2~10 個互不相同的十進制數字（已排序），將它們分成兩組，每組按任意順序組成一個整數（不得有前導零，除非該數為 0），使兩數差的絕對值最小。輸出最小差值。

解題思路

1. 數字個數 ≤ 10，全排列枚舉所有排列（10! = 3,628,800），可行。
2. 對每個排列，嘗試在中間位置劃分為兩數（長度盡量相等），計算差值，取最小。
3. 跳過前導零的排列：用 next_permutation 從第一個非零開頭的排列開始枚舉。

代碼實現

#include <bits/stdc++.h>
using namespace std;

int num[12];

int main() {
    int T; scanf("%d", &T); getchar();
    while (T--) {
        int cnt = 0; char ch;
        while ((ch = getchar()) != ' ') if (ch >= '0' && ch <= '9') num[cnt++] = ch - '0';
        if (cnt == 2) { printf("%d\n", abs(num[1] - num[0])); continue; }

        int ans = INT_MAX;
        // 確保首位非零
        while (num[0] == 0) next_permutation(num, num + cnt);
        do {
            int mid = (cnt + 1) >> 1; // 兩數長度盡量相等
            if (num[mid] == 0) continue; // 第二數首位不能為零
            int x = 0, y = 0;
            for (int i = 0; i < mid; ++i) x = x * 10 + num[i];
            for (int i = mid; i < cnt; ++i) y = y * 10 + num[i];
            ans = min(ans, abs(x - y));
        } while (next_permutation(num, num + cnt));
        printf("%d\n", ans);
    }
    return 0;
}

關鍵細節

• 輸入處理：數字間有空格，逐字符讀取非空格數字。
• 劃分點固定為 mid = (cnt+1)/2，因為要使差最小，兩數位數應盡量相等；若允許不等長分割需枚舉所有劃分點，但題目數據特性下中間劃分即可（經驗結論）。
• next_permutation 要求初始序列有序，輸入已保證遞增。
• 時間複雜度：O(cnt! × cnt)，cnt ≤ 10 可在 1 秒內通過。

範例

輸入: 0 1 2 4 6 7
輸出: 28  (如 204 和 176 差 28)

暴力枚舉雖簡單，但需注意前導零剪枝與劃分策略，否則易 TLE 或 WA。