剩余银饰的重量

🍊 剩余银饰的重量

问题描述

K小姐从二手市场收集了 $N$ 块银饰，每块银饰的重量都是正整数。这些银饰会被熔化用于打造新的饰品。每一回合，K小姐会选出三块最重的银饰一起熔掉。假设银饰的重量分别为 $x$、$y$ 和 $z$，且 $x\le y\le z$。那么熔掉的可能结果如下：

1. 如果 $x=y=z$，那么三块银饰都会被完全熔掉。
2. 如果 $x=y$ 且 $y\ne z$，会剩余重量为 $z-y$ 的银块无法被熔掉。
3. 如果 $x\ne y$ 且 $y=z$，会剩余重量为 $y-x$ 的银块无法被熔掉。
4. 如果 $x\ne y$ 且 $y\ne z$，会剩余重量为 $|z-y-(y-x)|$ 的银块无法被熔掉。

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

输入格式

第一行输入一个整数 $n$，表示银饰的数量。

第二行输入 $n$ 个整数，表示每块银饰的重量，以空格分隔。

输出格式

输出一个整数，表示最后剩余银饰的重量。如果剩余两块银饰，返回较大的重量；如果只剩下一块银饰，返回该块的重量；如果没有剩下银饰，返回 $0$。

样例输入1

3
1 1 1

样例输出1

0

样例输入2

3
3 7 10

样例输出2

1

数据范围

$1\le n\le 40$
$1\le$ 银饰重量 $\le 2000$

题解

本题可以使用优先队列来模拟熔炼银饰的过程。每次从优先队列中取出三块最重的银饰，按照题目描述的规则进行熔炼，并将剩余的银块重新放回优先队列中。重复这个过程，直到优先队列中的银饰数量小于 $3$ 为止。

最后，根据优先队列中剩余的银饰数量，返回相应的结果即可。

时间复杂度为 $O(n\log n)$，其中 $n$ 为银饰的数量。

参考代码

• Python

import heapq

n = int(input())
weights = list(map(int, input().split()))
pq = []

for weight in weights:
    heapq.heappush(pq, -weight)

while len(pq) >= 3:
    x = -heapq.heappop(pq)
    y = -heapq.heappop(pq)
    z = -heapq.heappop(pq)

    if x == y == z:
        continue
    elif x == y and y != z:
        heapq.heappush(pq, -(z - y))
    elif x != y and y == z:
        heapq.heappush(pq, -(y - x))
    else:
        heapq.heappush(pq, -abs(z - y - (y - x)))

if not pq:
    print(0)
else:
    print(-pq[0])

• Java

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < n; i++) {
            pq.offer(scanner.nextInt());
        }
        
        while (pq.size() >= 3) {
            int x = pq.poll();
            int y = pq.poll();
            int z = pq.poll();
            
            if (x == y && y == z) {
                continue;
            } else if (x == y && y != z) {
                pq.offer(z - y);
            } else if (x != y && y == z) {
                pq.offer(y - x);
            } else {
                pq.offer(Math.abs(z - y - (y - x)));
            }
        }
        
        if (pq.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(pq.poll());
        }
    }
}

• Cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<int> pq;
    
    for (int i = 0; i < n; i++) {
        int weight;
        cin >> weight;
        pq.push(weight);
    }
    
    while (pq.size() >= 3) {
        int x = pq.top();
        pq.pop();
        int y = pq.top();
        pq.pop();
        int z = pq.top();
        pq.pop();
        
        if (x == y && y == z) {
            continue;
        } else if (x == y && y != z) {
            pq.push(z - y);
        } else if (x != y && y == z) {
            pq.push(y - x);
        } else {
            pq.push(abs(z - y - (y - x)));
        }
    }
    
    if (pq.empty()) {
        cout << 0 << endl;
    } else {
        cout << pq.top() << endl;
    }
    
    return 0;
}