最小差距

时间限制 1000 ms
内存限制 128 MB
题目描述
　　给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。
　　例如，给定6个数字，0,1,2,4,6,7，你可以用它们组成一对数10和2467，当然，还可以组成其他的很多对数，比如210和764，204和176。这些对数中两个数差的绝对值最小的是204和176，为28。
　　给定N个不同的0~9之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？

输入数据
　　第一行包括一个数 T （T≤1000），为测试数据的组数。
　　每组数据包括两行，第一行为一个数 N （2≤N≤10），表示数字的个数。下面一行为 N 个不同的一位数字。
输出数据
　　T行，每行一个数，表示第 i 个数据的答案。即最小的差的绝对值。
样例输入
2
6
0 1 2 4 6 7
4
1 6 3 4
样例输出
28
5

#include<math.h>
#include<stdio.h>
#include <string.h>
#include<iostream>
#include <algorithm>
using namespace std;
int a[15];
int n;
int abs(int x) { return (x<0 ? -x : x); }
int step1() {
    if (a[1] == 0) swap(a[1], a[2]);
    int s1 = 0, s2 = 0;
    for (int i = 1; i <= n / 2 + 1; i++) s1 = s1 * 10 + a[i];
    for (int i = n; i >= n / 2 + 2; i--) s2 = s2 * 10 + a[i];
    return abs(s1 - s2);
}
int step2() {
    int book[15];
    int s1, s2;
    int ans = (1 << 31) - 1;
    for (int i = 2; i <= n; i++)
        if (a[i - 1]) {
            s1 = a[i], s2 = a[i - 1];
            memset(book, 0, sizeof(book));
            book[i] = book[i - 1] = 1;
            int l = 1, r = n;
            for (int j = 1; j <= (n - 2) / 2; j++) {
                while (book[l]) l++;
                while (book[r]) r--;
                book[l] = book[r] = 1;
                s1 = s1 * 10 + a[l]; s2 = s2 * 10 + a[r];
            }
            ans = min(ans, abs(s1 - s2));
        }
    return ans;
}
int main() {
    int groups;
    cin >> groups;
    while (groups--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sort(a + 1, a + 1 + n);
        if (n == 2) { 
            cout << a[2] - a[1] << endl;
            continue; 
        }
        if (n % 2 == 1) 
        cout << step1() << endl;
        else 
            cout << step2() << endl;
    }
}