解题思路

• 将每个箱子看作一对 (weight, value)。允许选择不超过 m 个箱子，目标是最大化： sum(weights_of_chosen) * min(value_of_chosen)。
• 核心做法:
  1. 按 value 从大到小排序，把当前箱子的 value 视作被选集合的最小价值阈值。
  2. 依次加入其 weight 到一个小根堆（只保留不超过 m 个最大的重量），同时维护堆中重量和 sumW。
  3. 在每一步，以当前 value 作为最小价值，候选答案为 sumW * value。 这样自然覆盖了选择 1…m 个箱子的所有情况（当堆里元素少于 m 时，即为“少于 m 个”）。
• 为什么正确：排序后，当前 value 作为最小值时，能搭配的只能是“价值 ≥ 当前 value”的物品；为了最大化乘积，需要在这些物品里取重量和最大的至多 m 个，堆正好完成这一点。

复杂度分析

• 排序 O(n log n)，每个元素最多入堆出堆一次，堆操作 O(log m)，总体 O(n log n + n log m)，在 m ≤ n 时可写成 O(n log n)。
• 额外空间为堆与已排序数组，O(n)；堆本身 O(m)。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意：给定 n 个箱子，每个有 weight 和 value，最多选 m 个，使
# sum(weight) * min(value) 最大，输出对 1e9+7 取模

import sys
import heapq
from ast import literal_eval

MOD = 1000000007

def max_total_value(weights, values, m):
    # 将 (value, weight) 按 value 降序
    pairs = sorted(zip(values, weights), reverse=True)
    min_heap = []  # 小根堆，存放当前选中的权重
    sumW = 0
    best = 0
    for v, w in pairs:
        # 加入一个重量
        heapq.heappush(min_heap, w)
        sumW += w
        # 若超过 m 个，只保留最大的 m 个重量
        if len(min_heap) > m:
            sumW -= heapq.heappop(min_heap)
        # 以当前 v 为最小价值，计算候选答案（当堆里元素 < m 时代表少选）
        best = max(best, sumW * v)
    return best % MOD

def read_int_list(line):
    line = line.strip()
    # 优先用 literal_eval 解析 1,2,3 / [1,2,3] 等格式
    try:
        arr = literal_eval(line)
        if isinstance(arr, int):
            return [arr]
        return list(arr)
    except Exception:
        # 退化为空格分割
        return list(map(int, line.replace(',', ' ').split()))

def main():
    data = sys.stdin.read().strip().splitlines()
    if not data:
        return
    n = int(data[0].strip())
    weights = read_int_list(data[1])
    values = read_int_list(data[2])
    m = int(data[3].strip())
    print(max_total_value(weights, values, m))

if __name__ == "__main__":
    main()

Java

// 题意：最多选 m 个箱子，使 sum(weights) * min(value) 最大，输出 mod
// 做法：按 value 降序，维护一个小根堆保存至多 m 个最大的 weight 与其和
import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 1000000007L;

    // 核心函数：返回答案（已取模）
    static long maxTotalValue(int[] weights, int[] values, int m) {
        int n = weights.length;
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = values[i];
            a[i][1] = weights[i];
        }
        // 按 value 降序
        Arrays.sort(a, (x, y) -> Integer.compare(y[0], x[0]));

        PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 小根堆
        long sumW = 0;
        long best = 0;

        for (int i = 0; i < n; i++) {
            int v = a[i][0];
            int w = a[i][1];
            minHeap.offer(w);
            sumW += w;
            // 只保留 m 个最大的重量
            if (minHeap.size() > m) {
                sumW -= minHeap.poll();
            }
            long cand = sumW * (long) v;
            if (cand > best) best = cand;
        }
        return best % MOD;
    }

    // 把逗号替换为空格后分割
    static int[] readIntArray(String line, int n) {
        line = line.trim().replace(",", " ");
        String[] sp = line.split("\\s+");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(sp[i]);
        return a;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        if (s1 == null || s1.trim().isEmpty()) return;
        int n = Integer.parseInt(s1.trim());

        String wLine = br.readLine();
        String vLine = br.readLine();
        String mLine = br.readLine();

        int[] weights = readIntArray(wLine, n);
        int[] values = readIntArray(vLine, n);
        int m = Integer.parseInt(mLine.trim());

        long ans = maxTotalValue(weights, values, m);
        System.out.println(ans);
    }
}

C++

// 题意：最多选 m 个箱子，使 sum(weights) * min(value) 最大
// 思路：按 value 降序遍历；用小根堆维护到目前为止价值>=当前value的重量中最大的至多 m 个
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

long long maxTotalValue(const vector<long long>& weights,
                        const vector<long long>& values, int m) {
    int n = (int)weights.size();
    vector<pair<long long,long long>> a(n);
    for (int i = 0; i < n; ++i) a[i] = {values[i], weights[i]};
    sort(a.begin(), a.end(), [](const auto& x, const auto& y){
        return x.first > y.first; // value 降序
    });

    priority_queue<long long, vector<long long>, greater<long long>> minh; // 小根堆
    long long sumW = 0, best = 0;
    for (int i = 0; i < n; ++i) {
        long long v = a[i].first, w = a[i].second;
        minh.push(w);
        sumW += w;
        if ((int)minh.size() > m) {
            sumW -= minh.top(); minh.pop();
        }
        long long cand = sumW * v;
        if (cand > best) best = cand;
    }
    return best % MOD;
}

// 将逗号替换为空格后用 stringstream 读取
vector<long long> readArrayLine(string line, int n) {
    for (char& c : line) if (c == ',') c = ' ';
    stringstream ss(line);
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) ss >> a[i];
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    if (!getline(cin, line)) return 0;
    int n = stoi(line);
    string wLine, vLine, mLine;
    getline(cin, wLine);
    getline(cin, vLine);
    getline(cin, mLine);

    vector<long long> weights = readArrayLine(wLine, n);
    vector<long long> values  = readArrayLine(vLine, n);
    int m = stoi(mLine);

    cout << maxTotalValue(weights, values, m) << "\n";
    return 0;
}

题目内容

小张拥有多箱货物，每箱具有不同的重量和价值。现有一收购商提出，将以最低一箱货物的价值作为整体收购价格，且允许小张最多出售 $m$ 箱货物。请协助小张计算，在此条件下，他能够获得的最大总价值是多少。数值可能较大，最终结果与 $1000000007$ 取余后输出.

总价值的计算方法:$m$ 箱货物的总重量乘上 $m$ 箱货物中价值最小值

输入描述

输入为 $4$ 行

第一行为一个整数 $n$ ，代表货物的箱子总数，$0<=n<=10^5$

第二行为一个整数序列，长度为 $n$ ，分别代表货物每箱的重量，重量范围: $0<= weight<= 10^5$

第三行为一个整数序列，长度为 $n$ ，分别代表货物每箱的价格,价格范围: $0<= value<= 10^7$

第四行为一个整数 $m$，代表最多卖出的货物箱数 $0<=m<=n$

输出描述

输出小张能获得最大价值，与 $1000000007$ 取余后输出

样例1

输入

6
2,11,3,6,5,8
5,9,3,9,7,5
3

输出

154

说明

分别选择重量和价格为 $[11,9],[6,9],[5,7]$ 三个箱子价值最大，总重量为 $11+6+5=22$ ，总价值 $22*7=154$

样例2

输入

3
5,7,3
2,9,3
2

输出

63

说明

分别选择重量和价格为 $[7,9]$ 的箱子价值最大，价值 $7*9=63$