题面描述

一个歌手需要从城市 $A$ 前往城市 $B$ 参加演出，必须在 $T$ 天内到达。途中会经过 $N$ 座城市，歌手不能往回走。每两座城市之间的行程天数已知。歌手在每座城市可以卖唱赚钱，卖唱的收入每天递减。歌手到达某座城市后的第二天才能开始卖唱，且如果今天卖唱，第二天才能出发。目标是计算歌手在 $T$ 天内最多能赚多少钱。

详细思路

1. 问题理解

• 目标：歌手需要在 $T$ 天内从 $A$ 城赶到 $B$ 城，途中经过 $N$ 座城市。每两座城市之间的行程天数已知，且歌手不能往回走。
• 卖唱规则：
  • 歌手到达某座城市后的第二天才能开始卖唱。
  • 如果今天卖唱，第二天才能出发。
  • 卖唱的收入每天递减：第一天赚 $M$，第二天赚 $M - D$，第三天赚 $M - 2D$，直到收入减少到 $0$ 为止。
• 问题：如何在 $T$ 天内分配卖唱天数，使得总收入最大化？

2. 问题分解

1. 计算总行程天数：

   • 从 $A$ 到 $B$ 的总行程天数是所有城市之间行程天数的总和。
   • 设总行程天数为 $totalTravelDays$。

2. 计算剩余天数：

   • 剩余天数 $remainingDays = T - totalTravelDays$。
   • 这些剩余天数可以分配给途经的 $N$ 座城市，用于卖唱。

3. 卖唱收入计算：

   • 对于每座城市，卖唱 $k$ 天的总收入为： $收入= M + (M - D) + (M - 2D) + \dots + (M - (k-1)D)$ 这是一个等差数列，其和为： $收入= k \cdot M - D \cdot \frac{(k-1) \cdot k}{2}$
   • 需要注意的是，收入不能为负数，因此当 $M - (k-1)D \leq 0$ 时，停止计算。

4. 分配剩余天数：

   • 目标是最大化总收入，因此需要将剩余天数分配给收入最高的天数。
   • 由于收入是递减的，优先选择收入高的天数进行分配。

3. 贪心策略

1. 收入递减性质：

   • 每座城市的卖唱收入是递减的，因此卖唱的天数越多，边际收益越低。
   • 为了最大化总收入，应该优先选择当前收入最高的天数。

2. 优先队列（堆）的使用：

   • 使用一个最大堆（优先队列）来存储所有可能的卖唱收入。
   • 对于每座城市，计算卖唱 $k$ 天的收入，并将这些收入存入堆中。
   • 每次从堆中取出最大的收入，累加到总收入中，直到剩余天数用完。

3. 算法步骤：

   • 遍历每座城市，计算卖唱 $k$ 天的收入，存入堆。
   • 从堆中取出最大的 $remainingDays$ 个收入，累加得到总收入。

cpp

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

using namespace std;

int main() {
    int T, N;
    cin >> T >> N;
    
    vector<int> travelDays(N + 1);
    for (int i = 0; i <= N; ++i) {
        cin >> travelDays[i];
    }
    
    vector<pair<int, int>> cities(N);
    for (int i = 0; i < N; ++i) {
        cin >> cities[i].first >> cities[i].second;
    }
    
    // 计算总行程天数
    int totalTravelDays = 0;
    for (int day : travelDays) {
        totalTravelDays += day;
    }
    
    // 剩余的天数可以用于卖唱
    int remainingDays = T - totalTravelDays;
    
    // 使用优先队列（最大堆）来存储每座城市的收入
    priority_queue<int> maxHeap;
    
    // 计算每座城市卖唱 k 天的总收入
    for (auto& city : cities) {
        int M = city.first;
        int D = city.second;
        int k = 0;
        while (M - k * D > 0 && k < remainingDays) {
            maxHeap.push(M - k * D);
            k++;
        }
    }
    
    // 从堆中取出最大的 remainingDays 个收入
    int totalIncome = 0;
    while (!maxHeap.empty() && remainingDays > 0) {
        totalIncome += maxHeap.top();
        maxHeap.pop();
        remainingDays--;
    }
    
    cout << totalIncome << endl;
    
    return 0;
}

python

import heapq

def main():
    T, N = map(int, input().split())
    travel_days = list(map(int, input().split()))
    cities = [tuple(map(int, input().split())) for _ in range(N)]
    
    total_travel_days = sum(travel_days)
    remaining_days = T - total_travel_days
    
    max_heap = []
    
    for M, D in cities:
        k = 0
        while M - k * D > 0 and k < remaining_days:
            heapq.heappush(max_heap, -(M - k * D))  # 使用负数模拟最大堆
            k += 1
    
    total_income = 0
    while max_heap and remaining_days > 0:
        total_income += -heapq.heappop(max_heap)
        remaining_days -= 1
    
    print(total_income)

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象用于读取输入
        Scanner sc = new Scanner(System.in);

        // 读取总天数 T 和城市数量 N
        int T = sc.nextInt();
        int N = sc.nextInt();

        // 读取每两座城市之间的行程天数
        int[] travelDays = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            travelDays[i] = sc.nextInt();
        }

        // 读取每座城市的卖唱收入 M 和递减值 D
        int[][] cities = new int[N][2];
        for (int i = 0; i < N; i++) {
            cities[i][0] = sc.nextInt(); // M
            cities[i][1] = sc.nextInt(); // D
        }

        // 计算总行程天数
        int totalTravelDays = 0;
        for (int day : travelDays) {
            totalTravelDays += day;
        }

        // 计算剩余可以用于卖唱的天数
        int remainingDays = T - totalTravelDays;

        // 创建一个最大堆（优先队列），用于存储每座城市的卖唱收入
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 遍历每座城市，计算卖唱 k 天的收入，并存入最大堆
        for (int[] city : cities) {
            int M = city[0]; // 第一天的收入
            int D = city[1]; // 每天收入的递减值
            int k = 0;       // 卖唱的天数

            // 计算卖唱 k 天的收入，直到收入为 0 或剩余天数用完
            while (M - k * D > 0 && k < remainingDays) {
                maxHeap.offer(M - k * D); // 将收入加入最大堆
                k++;
            }
        }

        // 计算总收入
        int totalIncome = 0;
        while (!maxHeap.isEmpty() && remainingDays > 0) {
            totalIncome += maxHeap.poll(); // 取出当前最大收入并累加
            remainingDays--;               // 剩余天数减 1
        }

        // 输出最大总收入
        System.out.println(totalIncome);
    }
}

题目内容

一个歌手准备从 $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

输入

10 2
1 1 2
120 20
90 10

输出

540

说明

总共$10$天，路上经过$2$座城市。

路上共花 $1+1+2=4$ 天

剩余$6$天最好的计划是在第一座城市待$3$天，在第二座城市待$3$天。

在第一座城市赚的钱：$120 + 100 + 80 = 300$

在第二座城市赚的钱：$90 + 80 + 70 = 240$

一共 $300 + 240 = 540$。