算法，蓝桥杯pta实战训练

Question

pta遇到的题，用C语言解决，各位智者解决一下，我已经尽力了，大一新生，有输入和输出格式样例
牛牛有N个雪球。第i个雪球 (1≤i≤N ) 的直径为 H。雪人由两个雪球组成，可以通过在下面堆叠一个雪球x和另一个不大于雪球x的雪球y来建造。此时雪人的高度等于两个雪球的直径之和。

牛牛从N个雪球 中选出四个不同的雪球，试着堆两个雪人。牛牛认为，两个雪人的身高差越小，两个雪人的关系就会越好。现在我们来帮助牛牛堆出最好的两个雪人。

编写一个程序，找出使用给定数量的N个雪球可以堆成的两个雪人之间的最小高度差。

输入格式:
第一行给出N 。
在第二行中，N个整数，每个整数H表示每个雪球的直径，用空格分开。
4≤N≤600
4≤H≤10^9
输出格式:
输出一个整数，表示可以制作的两个雪人之间的最小高度差。
输入样例

5
3 5 2 5 9

输出样例

1

样例解释：两个高度为 (2, 5) 和 (3, 5) 的雪人是最好的情况之一。|7-8| = 1

另一种情况是用 (2, 9) 和 (5, 5) 堆两个雪人。|11-10| = 1

Answer 1

基于Monster 组和GPT的调写：
这道题目可以使用贪心算法来解决。具体思路为：

首先将所有雪球按直径从小到大排序。

枚举所有的雪人组合，一共有 $\binom{N}{4}$ 种组合方式。

对于每一种组合方式，将四个雪球分成两对，分别计算出两个雪人的高度。

对两个雪人的高度差取绝对值，如果这个值比之前计算的所有值都要小，就更新最小值。

时间复杂度为 $O(N^4)$，可能会超时，但是由于 $N$ 的范围比较小，可以通过这种方法解决。

以下是参考实现，需要注意的是，由于直径最大可以达到 $10^9$，因此在计算两个雪球直径之和的时候，需要使用 long long 类型。

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 600
#define MAX_H ((long long)1e9)

int cmp(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int main() {
    int n, h[MAX_N];
    long long ans = MAX_H * 2;

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &h[i]);
    }
    qsort(h, n, sizeof(int), cmp);

    for (int i = 0; i < n - 3; ++i) {
        for (int j = i + 1; j < n - 2; ++j) {
            for (int k = j + 1; k < n - 1; ++k) {
                for (int l = k + 1; l < n; ++l) {
                    long long a = h[i] + h[l];
                    long long b = h[j] + h[k];
                    long long diff = llabs(a - b);
                    if (diff < ans) {
                        ans = diff;
                    }
                }
            }
        }
    }

    printf("%lld\n", ans);
    return 0;
}