POJ2718

Posted on | In ,

Smallest Difference

Solution sketch

基本上就是全排列後，中間切一半求差。

小心 leading zero 和 only zero 的 case。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
    int ncase;
    char str[100];
    fgets(str, 100, stdin);
    sscanf(str, "%d", &ncase);
    while (ncase--) {
        vector<int> inp;
        char str[100];
        fgets(str, 100, stdin);
        char *num = strtok(str, " ");
        while (num != NULL) {
            inp.push_back(atoi(num));
            num = strtok(NULL, " ");
        }
        int sz = inp.size();
        int res = INT_MAX;
        do {
            bool error = false;
            int r = 0, l = 0;
            for (int i = 0; i < sz / 2; i++) {
                if (sz > 1 && i == 0 && inp[i] == 0)
                    error = true;
                r *= 10;
                r += inp[i];
            }
            for (int i = sz / 2; i < sz; i++) {
                if (sz - sz / 2 > 1 && i == sz / 2 && inp[i] == 0)
                    error = true;
                l *= 10;
                l += inp[i];
            }
            if (error == false) {
                res = min(res, abs(r - l));
            }
        } while (next_permutation(inp.begin(), inp.end()));
        printf("%d\n", res);
    }
    return 0;
}

AC code

想太多了，竟然先想說對於所有的分堆可能，窮舉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
    int ncase;
    char str[100];
    fgets(str, 100, stdin);
    sscanf(str, "%d", &ncase);
    while (ncase--) {
        vector<int> inp;
        char str[100];
        fgets(str, 100, stdin);
        char *num = strtok(str, " ");
        while (num != NULL) {
            inp.push_back(atoi(num));
            num = strtok(NULL, " ");
        }
        int sz = inp.size();
        int res = INT_MAX;
        for (int i = 0; i < (1 << sz); i++) {
            if (__builtin_popcount(i) == (sz / 2)) {
                vector<int> left, right;
                for (int j = 0; j < sz; j++) {
                    if ((i >> j) & 1)
                        right.push_back(inp[j]);
                    else
                        left.push_back(inp[j]);
                }
                vector<int> r, l;
                if (sz / 2 == 1 && right[0] == 0) {
                    r.push_back(0);
                }
                do {
                    if (right[0] == 0)
                        continue;
                    int rnum = 0;
                    for (int j = 0; j < (int)right.size(); j++) {
                        rnum *= 10;
                        rnum += right[j];
                    }
                    r.push_back(rnum);
                } while (next_permutation(right.begin(), right.end()));
                if ((sz - sz / 2) == 1 && left[0] == 0) {
                    l.push_back(0);
                }
                do {
                    if (left[0] == 0)
                        continue;
                    int lnum = 0;
                    for (int j = 0; j < (int)left.size(); j++) {
                        lnum *= 10;
                        lnum += left[j];
                    }
                    l.push_back(lnum);
                } while (next_permutation(left.begin(), left.end()));
                for (int j = 0; j < (int)l.size(); j++) {
                    for (int k = 0; k < (int)r.size(); k++) {
                        res = min(res, abs(l[j] - r[k]));
                    }
                }
            }
        }
        printf("%d\n", res);
    }
    return 0;
}