题解 | #星际商人的贸易之旅#

题目链接

星际商人的贸易之旅

题目描述

一位星际商人拥有初始宇宙信用点 $C$ ，计划进行为期 $D$ 天的贸易活动。空间站中有 $N$ 种商品，第 $i$ 种商品的购买成本为 $Costs_i$ ，纯利润为 $Profits_i$ 。

贸易规则如下：

每日一易：每天最多购买一件商品。
资金约束：购买商品时，当前信用点必须不低于其成本。
即时交易：购买后立即贩卖，信用点更新为 $C_{current} + Profits_i$ 。
商品唯一：每种商品只有一件。

任务是规划 $D$ 天的贸易，最大化总利润。

输入:

第一行：贸易天数 $D$ 。
第二行：初始信用点 $C$ 。
第三行： $N$ 种商品的成本数组 $Costs$ 。
第四行： $N$ 种商品的利润数组 $Profits$ 。

输出:

一个整数，代表能赚取的最大总利润。

解题思路

这是一个典型的贪心问题。我们的目标是在有限的天数内最大化总利润。在每一天，我们都应该做出一个当前最优的决策，以期达到全局最优。

贪心策略

在任何一天，我们的购买能力都受限于当前的信用点。为了在未来能有更多、更好的选择（即能买得起成本更高、可能利润也更高的商品），我们当前的目标应该是最大化信用点的增长速度。

因此，在每一天，对于所有我们买得起的商品，我们都应该选择那个能带来最高利润的商品进行交易。这能让我们的资本增长最快，从而在接下来的日子里解锁更多的购买选项。

算法实现

直接在每一天都遍历所有商品来寻找最优选择效率不高。我们可以通过“排序 + 优先队列”的组合来优化这个过程。

预处理：
- 将商品的成本和利润配对成 (cost, profit) 的形式。
- 将所有商品按照成本 cost 从低到高进行排序。这样做的好处是，我们可以顺序地处理商品，随着我们资本的增加，越来越多的商品会“解锁”并变得可以购买。
每日决策：
- 我们使用一个大顶堆（Max-Heap / Priority Queue）来维护当前所有已解锁（买得起）但尚未购买的商品的利润。
- 我们从第一天开始，循环 $D$ 天： a. 更新候选池：遍历排好序的商品列表，将所有成本小于或等于当前信用点的商品，其利润加入到大顶堆中。 b. 做出最优选择：如果大顶堆不为空，说明我们至少有一个可交易的选择。我们从堆顶取出最大值（即当前可获得的最大利润），进行交易。 c. 更新状态：将取出的利润加到当前信用点上。 d. 如果大顶堆为空，说明当前信用点买不起任何尚未考虑的商品，后续的日子也无法再进行交易，可以直接结束循环。
结果：
- 最终的信用点减去初始信用点，即为最大总利润。

代码

c++
java
python

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

using namespace std;

struct Item {
    int cost;
    int profit;

    bool operator<(const Item& other) const {
        return cost < other.cost;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int d, c;
    cin >> d >> c;

    vector<int> costs;
    int n = 0;
    int temp;
    // 使用 while(cin >> temp) 读取不定长数组
    while (cin >> temp) {
        costs.push_back(temp);
        n++;
        if (cin.peek() == '\n') break;
    }

    vector<int> profits(n);
    for (int i = 0; i < n; ++i) {
        cin >> profits[i];
    }

    vector<Item> items(n);
    for (int i = 0; i < n; ++i) {
        items[i] = {costs[i], profits[i]};
    }

    sort(items.begin(), items.end());

    long long current_credits = c;
    priority_queue<int> available_profits;
    int item_idx = 0;

    for (int day = 0; day < d; ++day) {
        // 将所有买得起的商品利润放入优先队列
        while (item_idx < n && items[item_idx].cost <= current_credits) {
            available_profits.push(items[item_idx].profit);
            item_idx++;
        }

        // 如果有可买的商品，就买利润最高的那个
        if (!available_profits.empty()) {
            current_credits += available_profits.top();
            available_profits.pop();
        } else {
            // 买不起任何东西了，提前结束
            break;
        }
    }

    cout << current_credits - c << endl;

    return 0;
}

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Comparator;

class Item {
    int cost;
    int profit;

    public Item(int cost, int profit) {
        this.cost = cost;
        this.profit = profit;
    }
}

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

        int d = Integer.parseInt(sc.nextLine());
        long c = Long.parseLong(sc.nextLine());
        String[] costs_str = sc.nextLine().split(" ");
        String[] profits_str = sc.nextLine().split(" ");
        
        int n = costs_str.length;
        List<Item> items = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            items.add(new Item(Integer.parseInt(costs_str[i]), Integer.parseInt(profits_str[i])));
        }

        // 按成本升序排序
        items.sort(Comparator.comparingInt(item -> item.cost));

        long current_credits = c;
        // 大顶堆
        PriorityQueue<Integer> available_profits = new PriorityQueue<>(Collections.reverseOrder());
        int item_idx = 0;

        for (int day = 0; day < d; day++) {
            // 将所有买得起的商品利润放入优先队列
            while (item_idx < n && items.get(item_idx).cost <= current_credits) {
                available_profits.add(items.get(item_idx).profit);
                item_idx++;
            }

            // 如果有可买的商品，就买利润最高的那个
            if (!available_profits.isEmpty()) {
                current_credits += available_profits.poll();
            } else {
                // 买不起任何东西了，提前结束
                break;
            }
        }

        System.out.println(current_credits - c);
    }
}

import heapq

# 读取输入
d = int(input())
c = int(input())
costs = list(map(int, input().split()))
profits = list(map(int, input().split()))

n = len(costs)
items = sorted(zip(costs, profits))

current_credits = c
# Python的heapq是小顶堆，存入利润的负数来模拟大顶堆
available_profits_heap = []
item_idx = 0

for _ in range(d):
    # 将所有买得起的商品利润放入堆
    while item_idx < n and items[item_idx][0] <= current_credits:
        heapq.heappush(available_profits_heap, -items[item_idx][1])
        item_idx += 1
    
    # 如果有可买的商品，就买利润最高的那个
    if available_profits_heap:
        # 弹出负的最大利润（即最小的负数），再取反得到正的最大利润
        best_profit = -heapq.heappop(available_profits_heap)
        current_credits += best_profit
    else:
        # 买不起任何东西了，提前结束
        break

print(current_credits - c)

算法及复杂度

算法：贪心 + 排序 + 优先队列
时间复杂度： $O(N \cdot \log N + D \cdot \log N)$ ，其中 $N$ 是商品总数， $D$ 是交易天数。 $O(N \cdot \log N)$ 来自于初始的商品排序。循环最多进行 $D$ 次，每次从优先队列中取出一个元素耗时 $O(\log N)$ ；每个商品最多被加入优先队列一次，总耗时 $O(N \cdot \log N)$ 。
空间复杂度： $O(N)$ ，用于存储商品列表和优先队列。在最坏情况下，所有商品都可能被加入优先队列。