题目描述

小明有初始资金$m$，想在接下来最多$k$天内，从小卖部老板那里每天最多购买1件、共$k$天的机会中，每种商品最多购买一次。共有$n$种商品，编号$1\ldots n$，其中第$i$种商品的成本价为 $\text{cost}[i]$，利润为$\text{profit}[i]$。

• 购买一件商品后，会立即获得利润，将资金从原来的$x$变为$x$ - ${cost}[i]$ + (${cost}[i]$ + ${profit}[i]$) = $x$ + ${profit}[i]$。
• 每天最多购买 1 件，且不能赊账：购买时必须满足当前资金$\ge {cost}[i]$。
• 每种商品只有 1 件库存，购买后不可重复购买。

求在最多$k$天内，小明能够获得的最大总利润。

思路

本题的核心在于：每一天在当前资金范围内，选择利润最高的一件商品购买，因此使用贪心 + 最大堆（优先队列）来动态维护“当前可以买到的商品中利润最大的”。将所有商品按成本升序排序后，依次将当前资金能买到的商品加入堆，每天从堆中取出最大利润的商品购买，更新资金与利润，最多进行$k$天，最终得到最大累计利润。

算法步骤：

1. 把所有商品按成本升序排序。

2. 遍历每一天（最多$k$天）：

   • 将当前资金能买得起的商品加入最大堆（按利润排列）；
   • 若堆非空，从中取出利润最大者，更新资金与利润；
   • 若没有可买商品，提前终止。

C++

#include <bits/stdc++.h>
using namespace std;

// 主函数入口
int main() {
    int k, m;
    cin >> k >> m;
    vector<int> cost, profit;

    // 读取成本数组
    {
        string line;
        getline(cin, line); // 读掉换行
        getline(cin, line);
        istringstream iss(line);
        int x;
        while (iss >> x) cost.push_back(x);
    }
    // 读取利润数组
    {
        string line;
        getline(cin, line);
        istringstream iss(line);
        int x;
        while (iss >> x) profit.push_back(x);
    }

    int n = cost.size();
    vector<pair<int, int>> items;
    for (int i = 0; i < n; ++i) {
        items.emplace_back(cost[i], profit[i]); // (成本, 利润)
    }

    // 按成本升序排序
    sort(items.begin(), items.end());

    int money = m, profit_sum = 0;
    priority_queue<int> pq; // 最大堆：利润从高到低

    int idx = 0;
    for (int day = 0; day < k; ++day) {
        // 把当前能买得起的商品加入堆
        while (idx < n && items[idx].first <= money) {
            pq.push(items[idx].second); // 加入利润
            ++idx;
        }

        // 如果堆非空，就买利润最大的商品
        if (!pq.empty()) {
            int p = pq.top(); pq.pop();
            money += p;         // 资金增加
            profit_sum += p;    // 累加总利润
        } else {
            break; // 买不到任何商品，结束
        }
    }

    cout << profit_sum << '\n';
    return 0;
}

python

import heapq

def max_profit(k, m, cost, profit):
    items = list(zip(cost, profit))
    # 按成本升序排序
    items.sort()
    n = len(items)
    
    money = m
    total_profit = 0
    max_heap = []  # Python 默认是最小堆，用负号模拟最大堆
    idx = 0

    for day in range(k):
        # 将所有当前能买的商品利润加入堆
        while idx < n and items[idx][0] <= money:
            heapq.heappush(max_heap, -items[idx][1])
            idx += 1

        # 如果有可选商品，买利润最高的
        if max_heap:
            p = -heapq.heappop(max_heap)
            money += p
            total_profit += p
        else:
            break  # 没有商品可买，提前结束

    return total_profit

# 读入输入格式
k = int(input().strip())
m = int(input().strip())
cost = list(map(int, input().strip().split()))
profit = list(map(int, input().strip().split()))

# 输出最大利润
print(max_profit(k, m, cost, profit))

java

import java.util.*;

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

        int k = Integer.parseInt(sc.nextLine().trim()); // 天数
        int m = Integer.parseInt(sc.nextLine().trim()); // 初始资金
        String[] costStr = sc.nextLine().trim().split(" ");
        String[] profitStr = sc.nextLine().trim().split(" ");
        int n = costStr.length;

        // 构建商品列表：每个商品是 (成本, 利润)
        List<int[]> items = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int c = Integer.parseInt(costStr[i]);
            int p = Integer.parseInt(profitStr[i]);
            items.add(new int[]{c, p});
        }

        // 按成本升序排序
        items.sort(Comparator.comparingInt(a -> a[0]));

        int money = m;
        int totalProfit = 0;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int idx = 0;

        for (int day = 0; day < k; day++) {
            // 把能买的商品加入最大堆（利润最大优先）
            while (idx < n && items.get(idx)[0] <= money) {
                maxHeap.offer(items.get(idx)[1]);
                idx++;
            }

            // 若可买商品存在，买利润最大的
            if (!maxHeap.isEmpty()) {
                int p = maxHeap.poll();
                money += p;
                totalProfit += p;
            } else {
                break;
            }
        }

        System.out.println(totalProfit);
        sc.close();
    }
}

题目内容

快过年了，小明想要用工作攒下的钱 $m$ 做一点生意补贴家用。和小卖部老板达成协商，可以按成本价格给他提供 $n$ 种商品，让他到隔壁村去销售，其中商品 $i$ 的成本价为 $cost_i$ ;利润为 $profit_i$ ;.

由于小明没法携带太多商品，老板也不想在过年期间工作，所以小明每天最多能从老板那里进 $1$ 次货，每次买 $1$ 件商品，购买后的商品无法再次购买。

老板不接收赊账，每种商品只有 $1$ 件库存，请问小明在 $k$ 天中最多可以赚多少利润呢?

输入描述

共4行

第一行 $k$ ：表示小明可以做生意的天数，$1<=k<= 1000$

第二行 $m$ ：表示小明初始攒的钱，$0<= m<= 1000$

第三行 $cost$ ：表示每种商品的成本价，$0 <= cost[i]<=1000$

第四行 $profit$ ：表示每种商品的利润，$0<= profit[i] <= 1000$

其中，$1<= cost.length$, $profit.length <= 200$

输出描述

$k$ 天后小明可以赚取的利润

样例1

输入

3
2
2 5 7
2 5 7

输出

2

说明

小明初始有 $2$ 元，仅能购买 $0$ 号商品，第 $1$ 天可赚取 $2$ 元

第 $2$ 天小明有 $4$ 元，但剩下的商品他都买不起了，所以他最终只能赚取 $2$ 元

样例2

输入

2
2
2 3 5
1 2 5

输出

3

说明

小明初始有 $2$ 元，仅能购买 $0$ 号商品，第 $1$ 天可赚取 $1$ 元

第 $2$ 天小明有 $3$ 元，能购买 $0$ 号和 $1$ 号商品，选择购买 $1$ 号商品，可赚取 $2$ 元

所以小明两天共赚取了 $1+2=3$ 元