【Py/Java/C++/JS四种语言OD2023C卷真题】20天拿下华为OD笔试之【贪心+优先队列】2023C-贪心歌手【欧弟算法】全网注释最详细分类最全的华为OD真题题解

题目：20天拿下华为OD笔试之【贪心+优先队列】

给定一个正整数数组arr，代表每个工作的难度值。每个工作都可以选择立即开始或等待一天来完成。你需要找到最少的天数，在这些天数内可以完成所有工作。

注意：

1. 完成工作的难度值总是大于等于完成它所需要的天数。
2. 工作可以在任何非负整数时间点开始，但是必须连续完成。

例如：

输入：arr = [2, 4, 6, 8, 10]

输出：3

解释：可以选择在第1天，第2天，第4天完成工作。

输入：arr = [10, 15, 30, 20, 25]

输出：3

解释：可以选择在第1天，第2天，第4天完成工作。

输入：arr = [1, 2, 4, 5, 6, 7, 8, 9, 10]

输出：5

解释：可以选择在第1天，第2天，第4天，第5天，第10天完成工作。

请你设计一个算法，计算出最少需要的天数。

解决方案：

这是一个贪心加优先队列的问题。我们可以使用优先队列（最小堆）来保存工作，优先队列中的工作按照其完成的最早时间排序。然后我们从1开始迭代，如果当前有工作可以开始，我们就开始它。如果工作可以在当前这一天完成，我们就完成它。

以下是Python, Java, C++和JavaScript的解决方案：

Python:

from queue import PriorityQueue
 
def minDays(arr):
    pq = PriorityQueue()
    for work in arr:
        pq.put((work, 0))
    ans = 0
    while not pq.empty():
        day = 0
        while not pq.empty() and pq.queue[0][0] == day:
            work, _ = pq.get()
            day += work
        ans += 1
    return ans
 
# 测试代码
arr = [2, 4, 6, 8, 10]
print(minDays(arr))  # 输出：3

Java:

import java.util.PriorityQueue;
 
public class Solution {
    public int minDays(int[] arr) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int work : arr) {
            pq.offer(new int[]{work, 0});
        }
        int ans = 0;
        while (!pq.isEmpty()) {
            int day = 0;
            while (!pq.isEmpty() && pq.peek()[0] == day) {
                int[] work = pq.poll();
                day += work[0];
            }
            ans++;
        }
        return ans;
    }
 
    // 测试代码
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {2, 4, 6, 8, 10};
        System.out.println(solution.minDays(arr));  // 输出：3
    }
}

C++:

#include <queue>
#include <vector>
 
using namespace std;
 
int minDays(vector<int>& arr) {
    priority_queue<pair<int, int>> pq;
    for (int work : arr) {
        pq.emplace(work, 0);
    }
    int ans = 0;
    while (!