题解 | #货物堆放#

题目链接

货物堆放

题目描述

有 $n$ 种商品，每种有三元组 $\big(w_i, v_i, k_i\big)$ ：重量、初始体积、压缩系数。将它们自上而下堆成一条竖直货堆。设商品 $i$ 上方（不含自身）的总重量为 $W_i$ ，则其实际体积为 $v_i - k_i \cdot W_i$ 。希望通过调整堆放顺序，使所有商品实际体积之和最小。

解题思路

目标函数为 $\sum_{i=1}^{n} \big(v_i - k_i\cdot W_i\big) = \underbrace{\sum v_i}_{\text{常数}}\; - \; \sum k_i\cdot W_i.$ 因此等价于最大化 $\sum k_i\cdot W_i$ 。
若堆放顺序为 $p_1, p_2, \ldots, p_n$ （自上而下），则 $W_{p_j} = \sum_{t<j} w_{p_t}$ ，从而 $\sum_{j=1}^{n} k_{p_j}\cdot W_{p_j} = \sum_{1\le t<j\le n} w_{p_t}\cdot k_{p_j}.$ 对任意两件商品 $x,y$ ，若令 $x$ 在 $y$ 上方，则对这对商品贡献为 $w_x\cdot k_y$ ；反之为 $w_y\cdot k_x$ 。为了使总贡献最大，应当让较大的一个作为“在上方”的次序成立： $w_x\cdot k_y \ge w_y\cdot k_x \;\Longleftrightarrow\; \frac{w_x}{k_x} \ge \frac{w_y}{k_y}.$
结论：按比值 $\dfrac{w_i}{k_i}$ 从大到小排序（实现时用交叉乘比较 $w_i\cdot k_j$ 与 $w_j\cdot k_i$ 以避免精度），自上而下堆放，即可使总实际体积最小。
扫描计算答案：维护前缀重量 $S$ （表示“当前物品上方的总重量”），每次累加 $v_i - k_i\cdot S$ ，再令 $S\leftarrow S + w_i$ 。

代码

c++
java
python

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

struct Item { long long w, v, k; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; if (!(cin >> n)) return 0;
    vector<Item> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].w >> a[i].v >> a[i].k;

    sort(a.begin(), a.end(), [](const Item& A, const Item& B){
        __int128 lhs = (__int128)A.w * B.k;
        __int128 rhs = (__int128)B.w * A.k;
        if (lhs != rhs) return lhs > rhs; // 按 w/k 降序
        return A.w < B.w; // 次关键字不影响最优性
    });

    long long ans = 0;
    long long prefixW = 0; // 当前物品上方的总重量
    for (const auto& x : a) {
        ans += x.v - x.k * prefixW;
        prefixW += x.w;
    }
    cout << ans << '\n';
    return 0;
}

import java.util.*;
import java.math.*;

public class Main {
    static class Item { long w, v, k; Item(long w, long v, long k){ this.w=w; this.v=v; this.k=k; } }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Item[] a = new Item[n];
        for (int i = 0; i < n; i++) a[i] = new Item(sc.nextLong(), sc.nextLong(), sc.nextLong());
        Arrays.sort(a, (A, B) -> {
            BigInteger lhs = BigInteger.valueOf(A.w).multiply(BigInteger.valueOf(B.k));
            BigInteger rhs = BigInteger.valueOf(B.w).multiply(BigInteger.valueOf(A.k));
            int cmp = lhs.compareTo(rhs);
            if (cmp != 0) return -cmp; // 降序
            return Long.compare(A.w, B.w);
        });
        long ans = 0, prefixW = 0;
        for (Item x : a) { ans += x.v - x.k * prefixW; prefixW += x.w; }
        System.out.println(ans);
    }
}

from functools import cmp_to_key

n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]  # (w, v, k)

def cmp(a, b):
    w1, v1, k1 = a
    w2, v2, k2 = b
    x = w1 * k2
    y = w2 * k1
    if x != y:
        return -1 if x > y else 1  # 按 w/k 降序
    return -1 if w1 < w2 else (1 if w1 > w2 else 0)

items.sort(key=cmp_to_key(cmp))

ans = 0
prefixW = 0
for w, v, k in items:
    ans += v - k * prefixW
    prefixW += w

print(ans)

算法及复杂度

算法：按 $\dfrac{w_i}{k_i}$ 降序排序（用交叉乘比较），线性扫描维护前缀重量并累加 $v_i - k_i\cdot S$ 。
时间复杂度： $\mathcal{O}(n\log n)$ 。
空间复杂度： $\mathcal{O}(n)$ 。