题目链接

Smallest Difference POJ - 2718

思路

首先一个注意的点是这个题的输入，可以用getline, scanf, gets, 笔者选用scanf。

本题在《挑战程序设计竞赛》里归类是搜索 ，笔者2年前曾用过stl里的next_permutation卡时间过的，现如今手写dfs怎么都过不了，一怒之下贪心0ms贪过。思路如下：

按数的个数的奇偶性分类

1。奇数：拼凑两个数a1, a2, a1 > a2, 且a1比a2多一位，自然a1的最高位应最小，如果最小值为0则a1的最高位取次小。这样a1的最高位就填好了。此时a1的剩下数位要保证尽量小，a2剩下的数位要保证尽量大。

2。偶数：拼凑两个数a1,a2, a1 > a2, 且a1和a2一样长，自然a1和a2的最高位应该取相差最小的数， 但是注意a2的最高位不能有前导零（0除外），a1和a2的最高位确定之后，a1的剩下数位要保证尽量小，a2剩下的数位要保证尽量大。

时间复杂度

$$ O(1) $$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

char s[MAXN];
int a[MAXN];
int k, n;

int abs(int x) {
    if (x < 0) {
        x = -x;
    }
    return x;
}

int fun1() {
    n = k / 2 + 1;
    vector<int> b;
    for (int i = 1; i <= k; i++) {
        b.push_back(a[i]);
    }
    sort(b.begin(), b.end());
    if (b[0] == 0) {
        swap(b[0], b[1]);
    }
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        x *= 10;
        x += b[i];
    }
    for (int i = k - 1; i >= n; i--) {
        y *= 10;
        y += b[i];
    }
    return abs(x - y);
}

int gao(vector<int> &b, int pos) {
    int x = b[pos + 1];
    int y = b[pos];
    int num = 1;
    for (int i = 0; i < k; i++) {
        if (i == pos || i == pos + 1) {
            continue;
        }
        x *= 10;
        x += b[i];
        num++;
        if (num == n) {
            break;
        }
    }
    num = 1;
    for (int i = k - 1; i >= 0; i--) {
        if (i == pos || i == pos + 1) {
            continue;
        }
        y *= 10;
        y += b[i];
        num++;
        if (num == n) {
            break;
        }
    }

    return abs(x - y);
}

int fun2() {
    if (k == 2) {
        return abs(a[1] - a[2]);
    }
    n = k / 2;
    vector<int> b;
    for (int i = 1; i <= k; i++) {
        b.push_back(a[i]);
    }
    sort(b.begin(), b.end());
    int ans = INF;
    for (int i = 0; i < k - 1; i++) {
        if (b[i] == 0) {
            continue;
        }
        ans = min(ans, gao(b, i));
    }
    return ans;
}

int main() {
    int T;
    scanf("%d", &T);// don't forget &
    while (T--) {
        getchar();
        scanf("%[^\n]", s);
        int len = strlen(s);
        k = 0;
        for (int i = 0; i < len; i++) {
            if ('0' <= s[i] && s[i] <= '9') {
                a[++k] = s[i] - '0';
            }
        }
        if (k & 1) {
            printf("%d\n", fun1());
        } else {
            printf("%d\n", fun2());
        }
    }
    return 0;
}