华为OD 机试 - 贪心歌手（Java & Python & C++）

五分钟学算法

发布于 2024-04-14 09:03:18

6030

发布于 2024-04-14 09:03:18

文章被收录于专栏：五分钟学算法

本题练习地址：https://oj.algomooc.com/

一、题目描述与示例

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

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

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

输入描述

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

0 < T < 1000，0 < N < 100

第二行 N+1 个数字，中间用空格隔开，代表每两座城市之间耗费的时间，其总和<=T。

接下来 N 行，每行两个数字 M 和 D，中间用空格隔开。代表每个城市的收入预期。

0 < M < 1000，0 < D < 100

输出描述

一个数字。代表歌手最多可以赚多少钱。以回车结束

示例一

输入

输出

说明

总共 10 天，路上经过 2 座城市。路上共花 1+1+2=4 天。剩余 6 天最好的计划是在第一座城市待 3 天，在第二座城市待 3 天。在第一座城市赚的钱：120 + 100 + 80 = 300 在第二座城市赚的钱：90 + 80 + 70 = 240

共 300 +240 = 540

示例二

输入

输出

二、解题思路

题目的名字已经把这道题用的算法告诉你了——贪心。

题干非常长，得好好理解题意。

首先歌手能够卖唱的所有天数是固定的。假设总时间为T，花费在路上的时间数组为days，那么可以停下来卖唱的时间为X = T - sum(days)。这是很容易分析出来的结论。

那么为了能够赚更多的钱，我们一定要把X天都拉满，即尽可能地停留在某个城市赚钱。

这X天的分配实际上是任意的，停留在哪一个城市都行，只要停留够X天就肯定能赚到尽可能多的钱。实际上我们并不需要按照歌手的时间线来考虑问题，而是按照某一天能够在哪个城市获得的钱数最多来考虑问题的。

考虑例子：

停留的卖唱天数X = 3，第一个城市的起始金额M1 = 100，衰减速度D1 = 50，第二个城市的起始金额M2 = 80，衰减速度D1 = 40。我们会做如下分析：

M1 > M2，在第一个城市进行卖唱，赚的钱ans = 100，在第一个城市赚到的钱衰减为M1 = 100 - 50 = 50
M2 < M1，在第二个城市进行卖唱，赚的钱ans = 100 + 80，在第二个城市赚到的钱衰减为M2 = 80 - 40 = 40
M1 < M2，在第一个城市进行卖唱，赚的钱ans = 100 + 80 + 50，在第一个城市赚到的钱衰减为M1 = 50 - 50 = 0

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

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

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

构建一个以最大值为排序依据的优先队列（即大根堆）heap
将每一个城市的(M, D)储存在堆中。
循环X次，表示最多可以停留X天在进行卖唱。
1. 弹出堆顶元素M, D，此时可以赚到M，即更新ans += M
2. 计算衰减后该城市能够赚到的钱M -= D。
3. 如果M衰减了D之后，仍大于0，说明还有可能继续在这个城市赚钱，需要将(M, D)重新入堆
注意在循环中，必须判断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和衰减速度D
for _ in range(N):
    M, D = map(int, input().split())
    # 将(M, D)入堆，
    # 由于维护的是大根堆，所以储存的是(-M, D)
    heappush(heap, (-M, D))

# 可以卖唱的总天数X
X = 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 < N+1; i++) {
            days[i] = scanner.nextInt();
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); // Max heap
        for (int i = 0; i < N; i++) {
            int M = scanner.nextInt();
            int D = scanner.nextInt();
            heap.offer(new int[]{M, D});
        }
        int X = T - sum(days);
        int ans = 0;
        for (int i = 0; i < X; i++) {
            if (heap.isEmpty()) {
                break;
            }
            int[] city = heap.poll();
            int M = city[0];
            int D = city[1];
            ans += M;
            M -= D;
            if (M > 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;
    }
}

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
  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 < N; i++) {
    let [M, D] = input[i + 2].split(' ').map(Number);
    heap.offer([M, D]);
  }

  let X = T - days.reduce((a, b) => a + b, 0);
  let ans = 0;

  for (let i = 0; i < X; i++) {
    if (heap.isEmpty()) break;
    let city = heap.poll();
    let [M, D] = city;
    ans += M;
    M -= D;
    if (M > 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 < len) {
      let leftChild = idx * 2 + 1;
      let rightChild = idx * 2 + 2;
      let largest = idx;
      if (leftChild < len && this.comparator(this.heap[leftChild], this.heap[largest]) > 0) {
        largest = leftChild;
      }
      if (rightChild < len && this.comparator(this.heap[rightChild], this.heap[largest]) > 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]];
  }
}

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int T, N;
    cin >> T >> N;
    vector<int> days(N+1);
    for (int i = 0; i < N+1; i++) {
        cin >> days[i];
    }
    priority_queue<pair<int, int>> heap; // Max heap
    for (int i = 0; i < N; i++) {
        int M, D;
        cin >> M >> D;
        heap.push({M, D});
    }
    int X = T;
    for (int i = 0; i < N+1; i++) {
        X -= days[i];
    }
    int ans = 0;
    for (int i = 0; i < X; i++) {
        if (heap.empty()) {
            break;
        }
        auto city = heap.top();
        heap.pop();
        int M = city.first;
        int D = city.second;
        ans += M;
        M -= D;
        if (M > 0) {
            heap.push({M, D});
        }
    }
    cout << ans << endl;
    return 0;
}