题目描述

有 N 块二手市场收集的银饰，每块银饰的重量都是正整数，收集到的银饰会被熔化用于打造新的饰品。 每一回合，从中选出三块 最重的 银饰，然后一起熔掉。假设银饰的重量分别为 x 、y 和 z，且 x <= y <= z。那么熔掉的可能结果如下：

• 如果x == y == z，那么三块银饰都会被完全熔掉；
• 如果x == y且y != z，会剩余重量为z - y的银块无法被熔掉；
• 如果x != y且y == z，会剩余重量为y - x的银块无法被熔掉；
• 如果x != y且y != z，会剩余重量为z - y与y - x差值的银块无法被熔掉。

如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；如果只剩下一块，返回该块的重量；如果没有剩下，就返回 0。

输入描述

输入数据为两行

第一行为银饰数组长度 n，1 ≤ n ≤ 40，

第二行为 n 块银饰的重量，重量的取值范围为[1，2000]，重量之间使用空格隔开

输出描述

如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；如果只剩下一块，返回该块的重量；如果没有剩下，就返回 0。

示例一

输入

3
1 1 1
12

输出

0
1

说明

选出 1 1 1，得到 0，最终数组转换为 []，最后没有剩下银块，返回 0

示例二

输入

3
3 7 10
12

输出

1
1

说明

选出 3 7 10，需要计算 (7-3) 和 (10-7) 的差值，即(7-3)-(10-7)=1，所以数组转换为 [1]，剩余一块，返回该块重量，返回 1

思路

1. 读取输入：

   • 首先，从标准输入中读取银饰的数量 n。
   • 然后，用一个数组 weight[] 存储每块银饰的重量，通过循环读取并存储。

2. 排序银饰重量：

   • 使用 C 语言内置的 qsort 函数对 weight[] 数组进行降序排列，这样每次都能直接获取最重的三块银饰。

3. 熔炼逻辑：

   • 当银饰数量大于等于3时，进入熔炼循环。
     • 在每一次循环中，取出当前最重的三块银饰（下标为 0、1、2 的元素）。
     • 根据题目给出的熔炼规则计算可能剩余的银块重量，并将结果存储到变量 piece 中。
     • 如果没有剩余（piece == 0），则继续下一轮循环；否则，将剩余重量 piece 加入数组，并更新当前银饰数量 n，然后重新对数组进行排序。

4. 处理剩余银饰：

   • 循环结束后，根据剩余银饰的数量决定输出结果：
     • 如果没有剩余银饰（n == 0），输出 0；
     • 如果只剩一块银饰（n == 1），输出该块银饰的重量(输出weight[0])；
     • 如果剩余两块银饰（n == 2），比较这两块的重量并输出较大的那个重量(输出weight[0])。

代码

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

// 定义一个比较函数，用于对银饰重量进行降序排序
int cmp(const void *a, const void *b) {
    return *(int *)b - *(int *)a; // 按照从大到小的顺序排列
}

// 计算熔炼后可能剩余的银块重量
int res(int x, int y, int z) {
    if (x == y && y == z)
        return 0; // 如果三块重量相等，则完全熔化无剩余
    if (x == y && y != z)
        return z - y;
    // 如果两块较轻的重量相等，则剩余较重的一块减去较轻的一块重量
    if (x != y && y == z)
        return y - x;
    // 如果中间和最重的重量相等，则剩余中间的减去最轻的一块重量
    if (x != y && y != z)
        return abs((z - y) - (y - x));
    // 如果三块重量都不相等，则计算两者差值的绝对值作为剩余重量
}

int main() {
    int n;
    scanf("%d", &n); // 输入银饰的数量

    // 初始化银饰重量数组
    int weight[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &weight[i]); // 输入每一块银饰的重量
    }

    // 对银饰重量数组进行降序排序
    qsort(weight, n, sizeof(int), cmp);

    // 当银饰数量大于等于3时，持续熔炼
    while (n >= 3) {
        // 获取当前最重的三块银饰重量
        int x = weight[2];
        int y = weight[1];
        int z = weight[0];

        // 移除已熔炼的三块银饰，并将剩余银饰向前移动
        for (int i = 0; i < n - 3; i++) {
            weight[i] = weight[i + 3];
        }
        n -= 3;

        // 计算此次熔炼后的剩余重量，并将其加入数组（若有剩余）
        int piece = res(x, y, z);
        if (piece == 0)
            continue;
        else {
            weight[n++] = piece;
            qsort(weight, n, sizeof(int), cmp); // 再次对剩余银饰进行降序排序
        }
    }

    // 根据最终剩余的银饰数量输出结果
    if (n == 0) {
        printf("0\n"); // 若没有剩余则输出0
    } else {
        printf("%d\n", weight[0]); // 否则输出剩余银饰的重量（数组中的最大值）
    }
    return 0;
}