Fork me on GitHub

贪心算法_最小差距

发表于 | 分类于 | | 次阅读
给定一些不同的一位数字，你可以从这些数字中选择若干个，并将它们按一定顺序排列，组成一个整数，把剩下的数字按一定顺序排列，组成另一个整数。组成的整数不能以0开头（除非这个整数只有1位）。例如，给定6个数字，0,1,2,4,6,7，你可以用它们组成一对数10和2467，当然，还可以组成其他的很多对数，比如210和764，204和176。这些对数中两个数差的绝对值最小的是204和176，为28。给定N个不同的0-9之间的数字，请你求出用这些数字组成的每对数中，差的绝对值最小的一对（或多对）数的绝对值是多少？

Problem A. 最小差距

时间限制 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 个数据的答案。即最小的差的绝对值。

样例输入

1
2
3
4
5
2
6
0 1 2 4 6 7
4
1 6 3 4

样例输出

1
2
28
5

题解

首先将所有数字从小到大排序，接着这道题可以分三种情况考虑：
（1）只有两个数的情况：直接两数相减取绝对值即可。
（2）奇数个数的情况：首先保证第一个数字非0，如果为0，就将第一个数与第二个数交换位置，然后从左往右连续取n/2+1个数组成第一个整数，最后从右往左连续取n/2个数，即剩下的所有数组成另一个整数。这样所求得的一对整数的差的绝对值最小。
（3）偶数个数的情况：从左往右依次枚举，首先保证第一个数非0，如果为0，就从下一个数开始枚举；取第k个数作为第一个整数的第一个数字，取第k+1个数作为第二个整数的第一个数字；然后，对于剩下的数字，从右往左连续取n/2-1个数加入第一个整数中，从左往右连续取n/2-1个数加入第二个整数中；最后，取差的绝对值最小的一对整数。

AC代码

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int t, n, d[20], num1, num2;
int i, j, k, l, r;

int main() {
    scanf("%d", &t);
    for (i = 0; i < t; i++) {
        scanf("%d", &n);
        for (j = 1; j <= n; j++) {
            scanf("%d", &d[j]);
        }
        sort(d + 1, d + n + 1);
        if (n == 2) { // 两个数的情况
            printf("%d\n", abs(d[2] - d[1]));
        } else if (n % 2 == 1) { // 奇数个数的情况
            if (d[1] == 0) {
                swap(d[1], d[2]);
            }
            num1 = 0, num2 = 0;
            // 前n/2+1个数从左往右组成第一个整数
            for (j = 1; j <= n / 2 + 1; j++) {
                num1 = num1 * 10 + d[j];
            }
            // 后n/2个数从右往左组成第二个整数
            for (j = n; j >= n / 2 + 2; j--) {
                num2 = num2 * 10 + d[j];
            }
            printf("%d\n", abs(num1 - num2));
        } else { // 偶数个数的情况
            int result = 0x7fffffff;
            // 枚举，取第k个数加入第一个整数中，取第k+1个数加入第二个整数中
            for (j = 1; j < n; j++) {
                if (d[j] == 0) {
                    continue;
                }
                num1 = d[j], num2 = d[j + 1];
                // 从右往左遍历n/2-1个数加入第一个整数中
                // 从左往右遍历n/2-1个数加入第二个整数中
                l = 1, r = n;
                for (k = 0; k < n / 2 - 1; k++) {
                    if (l == j) l++;
                    if (l == j + 1) l++;
                    if (r == j + 1) r--;
                    if (r == j) r--;
                    num1 = num1 * 10 + d[r];
                    num2 = num2 * 10 + d[l];
                    l++, r--;
                }
                // 取差最小的值
                result = min(result, abs(num1 - num2));
            }
            printf("%d\n", result);
        }
    }
    return 0;
}
0%