华为OD机试：贪心歌手

题目描述

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

1.按照合同，他必须在 T 天内赶到

2.歌手途经 N 座城市

3.歌手不能往回走

4.每两座城市之间需要的天数都可以提前获知。

5.歌手在每座城市都可以在路边卖唱赚钱。

经过调研，歌手提前获知了每座城市卖唱的收入预期：

如果在一座城市第一天卖唱可以赚M，后续每天的收入会减少D（第二天赚的钱是 M - D，第三天是 M - 2D ...）。如果收入减少到 0 就不会再少了。

6.歌手到达后的第二天才能开始卖唱。如果今天卖过唱，第二天才能出发。

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

输入描述

第一行两个数字 T 和 N，中间用空格隔开。

T 代表总天数，0 < T < 1000

N 代表路上经过 N 座城市，0 < N < 100

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

其总和 ≤ T。

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

0 < M < 1000

0 < D < 100

输出描述

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

用例

题目解析

1.首先计算歌手在每个城市停留的天数。由于歌手到达后的第二天才能开始卖唱，所以每个城市的停留天数为 T - 每两座城市之间耗费的时间。

2.然后计算歌手在每个城市能赚多少钱。根据题目描述，歌手在第一天可以赚 M，后续每天的收入会减少 D。我们可以使用一个循环来计算歌手在每个城市能赚多少钱。

3.最后比较歌手在不同城市停留的天数和能赚的钱，找出最大的收益。

JS算法源码
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

async function getLine() {
  return new Promise((resolve, reject) => {
    rl.on('line', (line) => {
      resolve(line);
    });
  });
}

async function main() {
  const [t, n] = (await getLine()).split(" ").map(Number);
  const roadCost = (await getLine()).split(" ").map(Number).reduce((a, b) => a + b);
  const mds = [];
  for (let i = 0; i < n; i++) {
    mds.push((await getLine()).split(" ").map(Number));
  }
  const remain = t - roadCost;
  if (remain <= 0) {
    console.log(0);
    return;
  }
  const pq = new MinHeap();
  for (let [m, d] of mds) {
    while (m > 0) {
      if (pq.size >= remain) {
        if (m > pq.peek()) {
          pq.pop();
        } else {
          break;
        }
      }
      pq.push(m);
      m -= d;
    }
  }
  const ans = pq.items.reduce((a, b) => a + b);
  console.log(ans);
}

class MinHeap {
  constructor() {
    this.items = [];
    this.size = 0;
  }
  push(item) {
    this.items.push(item);
    this.size++;
    this.bubbleUp(this.size - 1);
  }
  pop() {
    const min = this.items[0];
    const last = this.items.pop();
    this.size--;
    if (this.size > 0) {
      this.items[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }
  peek() {
    return this.items[0];
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.items[parentIndex] > this.items[index]) {
        [this.items[parentIndex], this.items[index]] = [this.items[index], this.items[parentIndex]];
        index = parentIndex;
      } else {
        break;
      }
    }
  }
  bubbleDown(index) {
    while (true) {
      const leftChildIndex = index * 2 + 1;
      const rightChildIndex = index * 2 + 2;
      let minIndex = index;
      if (leftChildIndex < this.size && this.items[leftChildIndex] < this.items[minIndex]) {
        minIndex = leftChildIndex;
      }
      if (rightChildIndex < this.size && this.items[rightChildIndex] < this.items[minIndex]) {
        minIndex = rightChildIndex;
      }
      if (minIndex === index) {
        break;
      }
      [this.items[minIndex], this.items[index]] = [this.items[index], this.items[minIndex]];
      index = minIndex;
    }
  }
}

void (async function () {
  await main();
})();

Java算法源码
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int t;
    static int n;
    static int roadCost;
    static int[][] mds;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        t = sc.nextInt();
        n = sc.nextInt();

        roadCost = 0;
        for (int i = 0; i < n + 1; i++) {
            roadCost += sc.nextInt();
        }

        mds = new int[n][2];
        for (int i = 0; i < n; i++) {
            mds[i][0] = sc.nextInt();
            mds[i][1] = sc.nextInt();
        }

        System.out.println(getResult());
    }

    public static int getResult() {
        int remain = t - roadCost;

        if (remain <= 0) {
            return 0;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a - b);

        for (int[] md : mds) {
            int m = md[0];
            int d = md[1];

            while (m > 0) {
                if (pq.size() >= remain) {
                    if (m > pq.peek()) {
                        pq.poll();
                    } else {
                        break;
                    }
                }

                pq.add(m);
                m -= d;
            }
        }

        return pq.stream().reduce(Integer::sum).orElse(0);
    }
}

Python算法源码
import heapq

t, n = map(int, input().split())
road_cost = sum(map(int, input().split()))
mds = [list(map(int, input().split())) for _ in range(n)]

def get_result():
    remain = t - road_cost
    if remain <= 0:
        return 0

    pq = []
    for m, d in mds:
        while m > 0:
            if len(pq) >= remain:
                if m > pq[0]:
                    heapq.heappop(pq)
                else:
                    break
            heapq.heappush(pq, m)
            m -= d

    return sum(pq)

print(get_result())

C算法源码
 #include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *((int *) b) - *((int *) a);
}

void processRoadCosts(int t, int n, int *roadCosts) {
    int totalCost = 0;
    for (int i = 0; i < n + 1; i++) {
        scanf("%d", &roadCosts[i]);
        totalCost += roadCosts[i];
    }

    int remainingTime = t - totalCost;

    if (remainingTime <= 0) {
        printf("0\n");
        exit(0);
    }

    int pq[remainingTime + 1];
    int pqSize = 0;

    for (int i = 0; i < n; i++) {
        int m, d;
        scanf("%d %d", &m, &d);

        while (m > 0) {
            if (pqSize >= remainingTime) {
                if (m > pq[pqSize - 1]) {
                    pqSize--;
                } else {
                    break;
                }
            }

            pq[pqSize++] = m;
            qsort(pq, pqSize, sizeof(int), compare);

            m -= d;
        }
    }

    int ans = 0;
    for (int i = 0; i < pqSize; i++) {
        ans += pq[i];
    }

    printf("%d\n", ans);
}

int main() {
    int t, n;
    scanf("%d %d", &t, &n);

    int roadCosts[n + 1];
    processRoadCosts(t, n, roadCosts);

    return 0;
}