返回目录

题目描述

一个歌手准备从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. 最大化每天收益：对于每个城市，根据其收入预期M和收入递减值D，可以计算出如果在该城市卖唱，每一天的收益是多少。随着时间的推移，这个城市的日收益会递减。在这个过程中，算法每天都会计算并尝试选择当天的最大可能收益。
2. 选择最佳卖唱天数：由于总天数T是有限的，所以需要在所有可选的卖唱天数中挑选出最有利的组合。这里的贪心选择是通过优先队列（最小堆）来实现的。优先队列中存储的是当前选择的卖唱天数的收益。如果遇到一个新的天数其收益比队列中最小的收益要高，那么就替换掉这个最小收益的天数。这样，我们总是保持了收益最大化的天数组合。

具体 步骤

1. 初始化一个优先队列，用于记录每天的收益。优先队列的特性是，队列中的元素总是按照一定的顺序排列，这里是按照收益的大小排列。
2. 遍历每个城市，对于每个城市，计算从第一天开始每天的收益，并将其加入优先队列。
3. 如果优先队列的大小超过了剩余的天数，那么就取出优先队列中最小的收益，并与当天的收益进行比较。如果当天的收益更高，那么就将最小的收益移出队列，并将当天的收益加入队列。这样做的目的是，始终保持队列中的元素是最高的收益。
4. 当收益为0时，即当前城市的收益已经减少到0，那么就不再在该城市卖唱，跳出循环，继续处理下一个城市。
5. 最后，将优先队列中的所有收益相加，得到最大收益，并输出。

核心思想是贪心算法，即每一步都做出在当前看来最好的选择，最终得到的就是全局最优解。

python算法源码

import heapq

# 输入总天数和城市数量
T, N = map(int, input().split())

# 输入每两座城市之间耗费的时间
travelDays = list(map(int, input().split()))

# 输入每个城市的收入预期和收入递减值
M = []
D = []
for _ in range(N):
    m, d = map(int, input().split())
    M.append(m)
    D.append(d)

# 计算必须花费的路程时间
roadCost = sum(travelDays)
remain = T - roadCost
earningsQueue = []

# 遍历每个城市
for i in range(N):
    days = 0
    while True:
        # 计算今天的收益
        profitToday = max(M[i] - days * D[i], 0)
        if len(earningsQueue) < remain:
            heapq.heappush(earningsQueue, profitToday)
        else:
            if earningsQueue and profitToday > earningsQueue[0]:
                heapq.heappop(earningsQueue)
                heapq.heappush(earningsQueue, profitToday)
        if profitToday == 0:
            break
        days += 1

# 计算总收益
maxEarnings = sum(earningsQueue)
print(maxEarnings)

C算法源码

#include <stdio.h>
#include <stdlib.h>

// 比较函数用于排序
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int T, N;
    // 输入总天数和城市数量
    scanf("%d %d", &T, &N);

    // 动态分配内存存储每两座城市之间耗费的时间
    int *travelDays = (int *)malloc((N + 1) * sizeof(int));
    for (int i = 0; i <= N; i++) {
        // 输入每两座城市之间耗费的时间
        scanf("%d", &travelDays[i]);
    }

    // 动态分配内存存储每个城市的收入预期和收入递减值
    int *M = (int *)malloc(N * sizeof(int));
    int *D = (int *)malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        // 输入每个城市的收入预期和收入递减值
        scanf("%d %d", &M[i], &D[i]);
    }

    // 计算必须花费的路程时间
    int roadCost = 0;
    for (int i = 0; i <= N; i++) {
        roadCost += travelDays[i];
    }
    // 可用于卖唱赚钱的时间
    int remain = T - roadCost;

    // 动态分配内存存储每天的收益
    int *earningsQueue = (int *)malloc(remain * sizeof(int));
    int queueSize = 0; // 记录收益队列的大小

    // 遍历每个城市
    for (int i = 0; i < N; i++) {
        int days = 0; // 当前城市卖唱的天数
        while (1) {
            // 计算今天的收益
            int profitToday = M[i] - days * D[i] > 0 ? M[i] - days * D[i] : 0;
            if (queueSize < remain) {
                // 如果收益队列未满，直接加入
                earningsQueue[queueSize++] = profitToday;
                // 使用快速排序维护最小堆性质
                qsort(earningsQueue, queueSize, sizeof(int), compare);
            } else {
                // 如果收益队列已满
                if (queueSize > 0 && profitToday > earningsQueue[0]) {
                    // 如果今天的收益比最小收益大，替换最小收益并重新排序
                    earningsQueue[0] = profitToday;
                    qsort(earningsQueue, queueSize, sizeof(int), compare);
                }
            }
            if (profitToday == 0) break; // 如果收益为0，不再卖唱
            days++; // 卖唱天数加1
        }
    }

    // 计算总收益
    int maxEarnings = 0;
    for (int i = 0; i < queueSize; i++) {
        maxEarnings += earningsQueue[i];
    }

    // 输出总收益
    printf("%d\n", maxEarnings);

    // 释放动态分配的内存
    free(travelDays);
    free(M);
    free(D);
    free(earningsQueue);

    return 0;
}

Java算法源码

import java.util.Arrays;
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[] travelDays = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            travelDays[i] = scanner.nextInt();
        }

        // 输入每个城市的收入预期和收入递减值
        int[] M = new int[N];
        int[] D = new int[N];
        for (int i = 0; i < N; i++) {
            M[i] = scanner.nextInt();
            D[i] = scanner.nextInt();
        }

        // 计算必须花费的路程时间
        int roadCost = Arrays.stream(travelDays).sum();
        int remain = T - roadCost;

        // 使用优先队列存储收益，实现最小堆
        PriorityQueue<Integer> earningsQueue = new PriorityQueue<>();

        // 遍历每个城市
        for (int i = 0; i < N; i++) {
            int days = 0;
            while (true) {
                // 计算今天的收益
                int profitToday = Math.max(M[i] - days * D[i], 0);
                if (earningsQueue.size() < remain) {
                    earningsQueue.offer(profitToday);
                } else {
                    if (!earningsQueue.isEmpty() && profitToday > earningsQueue.peek()) {
                        earningsQueue.poll();
                        earningsQueue.offer(profitToday);
                    }
                }
                if (profitToday == 0) break;
                days++;
            }
        }

        // 计算总收益
        int maxEarnings = 0;
        for (int earnings : earningsQueue) {
            maxEarnings += earnings;
        }

        // 输出总收益
        System.out.println(maxEarnings);
    }
}