华为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; }