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

���华为OD考试扣扣交流群可加：948025485

可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题

绿色聊天软件戳 od1336了解算法冲刺训练

文章目录

• 题目描述与示例
• • • 输入描述
    • 输出描述
    • 示例一
    • • 输入
      • 输出
      • 说明
      • 示例二
      • • 输入
        • 输出
        • 解题思路
        • 代码
        • • Python
          • Java
          • C++
          • JavaScript
          • 时空复杂度
          • 华为OD算法/大厂面试高频题算法练习冲刺训练

            题目描述与示例

            歌手准备从 A 城去 B 城参加演出

            1. 按照合同，他必须在 T 天内赶到。
            2. 歌手途径 N 座城市。
            3. 歌手不能往回走。
            4. 每两座城市之间需要的天数都可以提前获知。
            5. 歌手在每座城市都可以在路边卖唱赚钱。经过调研，歌手提前获知了每座城市卖唱的收入预期。如果在一座城市第一天卖唱可以赚 M，后续每天的收入会减少 D (第二天赚的钱是 M-D，第三天是 M-2D…)。如果收入减到 0 就不会再少了。
            6. 歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。

            问贪心的歌手最多可以赚多少钱?

            输入描述

            第一行两个数字 T 和 N，中间用空格隔开，T 代表总天数； N 代表路上经过 N 座城市;

            0  
            第二行 N+1 个数字，中间用空格隔开，代表每两座城市之间耗费的时间，其总和 M2，在第一个城市进行卖唱，赚的钱ans = 100，在第一个城市赚到的钱衰减为M1 = 100 - 50 = 50

          • M2
          • M1

            那么X = 3就用完了，最多可以赚ans = 100 + 80 + 50 = 230。

            虽然真正的时间线为1(两天) -> 2(一天)，但是分析问题时我们的过程是1(一天) -> 2(一天) -> 1(一天)，但也能够计算出正确的答案。

            上述过程涉及到动态维护最大值的情形，很显然可以使用优先队列来维护该过程。具体过程如下：

            1. 构建一个以最大值为排序依据的优先队列（即大根堆）heap
            2. 将每一个城市的(M, D)储存在堆中。
            3. 循环X次，表示最多可以停留X天在进行卖唱。
               1. 弹出堆顶元素M, D，此时可以赚到M，即更新ans += M
               2. 计算衰减后该城市能够赚到的钱M -= D。
               3. 如果M衰减了D之后，仍大于0，说明还有可能继续在这个城市赚钱，需要将(M, D)重新入堆
            4. 注意在循环中，必须判断heap的长度是否大于0。如果等于0，说明优先队列中无元素，所有的城市赚的钱都衰减到0了，此时可以直接退出循环。

            不熟悉优先队列的同学，每一次最大值挑选完衰减后再次插入原数组的操作，也可以直接用排序的API来完成。由于插入完毕后至多只有一个元素是无序的，加上N的最大值只有100，因此这里直接使用排序并不会比优先队列慢很多。

            代码

            Python

            # # 题目：【贪心】2023C-贪心歌手# # 分值：200# # 作者：闭着眼睛学数理化# # 算法：贪心，优先队列# # 代码看不懂的地方，请直接在群上提问from heapq import heappush, heappop# 总天数，城市数T, N = map(int, input().split())# 路程天数days = list(map(int, input().split()))# 初始化一个大根堆heap = list()# N个城市的初始金额M和衰减速度Dfor _ in range(N):    M, D = map(int, input().split())    # 将(M, D)入堆，    # 由于维护的是大根堆，所以储存的是(-M, D)    heappush(heap, (-M, D))# 可以卖唱的总天数XX = T - sum(days)ans = 0# 遍历X天for i in range(X):    # 如果堆中无元素，则说明所有的城市赚的钱都衰减到0了    # 直接退出循环    if len(heap) == 0:        break    # 弹出堆中绝对值最大的M    M, D = heappop(heap)    # 之前储存的M是负数，改为正数    M = -M    # 选择在这个城市卖唱，可以赚到M    ans += M    # 赚完了M，需要衰减D，更新M的值    M -= D    # 如果M衰减了D之后，仍大于0，说明还有可能继续在这里赚钱，重新入堆    if M > 0:        heappush(heap, (-M, D))print(ans)

            Java

            import java.util.PriorityQueue;import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int T = scanner.nextInt();        int N = scanner.nextInt();        int[] days = new int[N+1];        for (int i = 0; i  Integer.compare(b[0], a[0])); // Max heap        for (int i = 0; i  0) {                heap.offer(new int[]{M, D});            }        }        System.out.println(ans);    }    private static int sum(int[] arr) {        int sum = 0;        for (int num : arr) {            sum += num;        }        return sum;    }}

            C++

            #include #include #include using namespace std;int main() {    int T, N;    cin >> T >> N;    vector days(N+1);    for (int i = 0; i > days[i];    }    priority_queue heap; // Max heap    for (int i = 0; i > M >> D;        heap.push({M, D});    }    int X = T;    for (int i = 0; i  0) {            heap.push({M, D});        }    }    cout   input: process.stdin,  output: process.stdout});let input = [];rl.on('line', line = {  input.push(line);}).on('close', () = {  let [T, N] = input[0].split(' ').map(Number);  let days = input[1].split(' ').map(Number);  let heap = new PriorityQueue((a, b) => a[0] - b[0]); // Max heap  for (let i = 0; i  a + b, 0);  let ans = 0;  for (let i = 0; i  0) heap.offer([M, D]);  }  console.log(ans);});class PriorityQueue {  constructor(comparator) {    this.comparator = comparator;    this.heap = [];  }  offer(val) {    this.heap.push(val);    this.bubbleUp(this.heap.length - 1);  }  poll() {    if (!this.isEmpty()) {      let len = this.heap.length;      this.swap(0, len - 1);      let val = this.heap.pop();      this.bubbleDown(0);      return val;    }  }  isEmpty() {    return this.heap.length === 0;  }  bubbleUp(idx) {    while (idx > 0) {      let parent = Math.floor((idx - 1) / 2);      if (this.comparator(this.heap[idx], this.heap[parent]) > 0) {        this.swap(idx, parent);        idx = parent;      } else {        break;      }    }  }  bubbleDown(idx) {    let len = this.heap.length;    while (idx  0) {        largest = leftChild;      }      if (rightChild  0) {        largest = rightChild;      }      if (largest !== idx) {        this.swap(idx, largest);        idx = largest;      } else {        break;      }    }  }  swap(i, j) {    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];  }}

            时空复杂度

            时间复杂度：O(XlogN)。优先队列单次插入操作的时间复杂度为O(logN)

            空间复杂度：O(N)。优先队列最多时储存N个元素。

            ---

            华为OD算法/大厂面试高频题算法练习冲刺训练

            • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

            • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

            • 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

            • 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

            • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

            • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

            • 绿色聊天软件戳 od1336了解更多