最新华为OD机试真题-剩余银饰的重量(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🎧 剩余银饰的重量
问题描述
K小姐从二手市场收集了 块银饰,每块银饰的重量都是正整数。这些银饰会被熔化用于打造新的饰品。每一回合,K小姐会选出三块最重的银饰一起熔掉。假设银饰的重量分别为
、
和
,且
。那么熔掉的可能结果如下:
- 如果
,那么三块银饰都会被完全熔掉。
- 如果
且
,会剩余重量为
的银块无法被熔掉。
- 如果
且
,会剩余重量为
的银块无法被熔掉。
- 如果
且
,会剩余重量为
的银块无法被熔掉。
最后,如果剩余两块银饰,返回较大的重量(若两块重量相同,返回任意一块皆可);如果只剩下一块银饰,返回该块的重量;如果没有剩下银饰,就返回 。
输入格式
第一行输入一个整数 ,表示银饰的数量。
第二行输入 个整数,表示每块银饰的重量,以空格分隔。
输出格式
输出一个整数,表示最后剩余银饰的重量。如果剩余两块银饰,返回较大的重量;如果只剩下一块银饰,返回该块的重量;如果没有剩下银饰,返回 。
样例输入1
3
1 1 1
样例输出1
0
样例输入2
3
3 7 10
样例输出2
1
数据范围
银饰重量
题解
本题可以使用优先队列来模拟熔炼银饰的过程。每次从优先队列中取出三块最重的银饰,按照题目描述的规则进行熔炼,并将剩余的银块重新放回优先队列中。重复这个过程,直到优先队列中的银饰数量小于 为止。
最后,根据优先队列中剩余的银饰数量,返回相应的结果即可。
时间复杂度为 ,其中
为银饰的数量。
参考代码
- 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;
}
#华为##华为od题库##华为OD华为招聘##华为OD##华为OD机试算法题库#最新华为OD机试-D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测