题解 | #货物堆放#

题目链接

题目描述

有 $N$ 种不同的商品，每种商品有重量 $w$ 、初始体积 $v$ 和压缩系数 $c$ 三个参数。当一个商品上方（不含自身）的总重量为 $W_a$ 时，其体积会变为 $v - W_a \cdot c$ 。要求找到一种堆放顺序，使得所有商品最终的实际体积之和最小。

解题思路

这是一个可以通过贪心策略解决的排序问题。我们的目标是最小化所有商品实际体积的总和。

设商品的堆放顺序从下到上为 $p_1, p_2, ..., p_N$ 。

第 $i$ 个商品 $p_i$ 上方的总重量为 $W_{p_i} = \sum_{j=i+1}^{N} w_{p_j}$ 。

该商品的实际体积为 $V_{p_i} = v_{p_i} - W_{p_i} \cdot c_{p_i}$ 。

总的实际体积为 $V_{total} = \sum_{i=1}^{N} (v_{p_i} - W_{p_i} \cdot c_{p_i}) = (\sum_{i=1}^{N} v_{p_i}) - (\sum_{i=1}^{N} W_{p_i} \cdot c_{p_i})$ 。

由于 $\sum v_{p_i}$ 是一个定值，不受排序影响，因此要最小化 $V_{total}$ ，我们必须最大化 $\sum_{i=1}^{N} W_{p_i} \cdot c_{p_i}$ 。

邻项交换法证明

我们可以使用邻项交换法来推导贪心排序的准则。

假设在某个最优序列中，存在两个相邻的物品 $i$ 和 $j$ ，其中 $j$ 紧邻着 $i$ 的上方。设它们上方所有物品的总重量为 $W_a$ 。

原始顺序 ( $i$ 在下， $j$ 在上):
- $j$ 上方的重量为 $W_a$ 。
- $i$ 上方的重量为 $W_a + w_j$ 。
- 它们对 $\sum W \cdot c$ 的贡献为 $(W_a + w_j) \cdot c_i + W_a \cdot c_j$ 。
交换后 ( $j$ 在下， $i$ 在上):
- $i$ 上方的重量为 $W_a$ 。
- $j$ 上方的重量为 $W_a + w_i$ 。
- 它们对 $\sum W \cdot c$ 的贡献为 $(W_a + w_i) \cdot c_j + W_a \cdot c_i$ 。

为了最大化 $\sum W \cdot c$ ，我们希望原始顺序的贡献更大，即：

$(W_a + w_j) \cdot c_i + W_a \cdot c_j > (W_a + w_i) \cdot c_j + W_a \cdot c_i$

展开并消去相同项 $W_a \cdot c_i$ 和 $W_a \cdot c_j$ ，得到： $w_j \cdot c_i > w_i \cdot c_j$

这个不等式是 $i$ 应该在 $j$ 下方的条件。为了避免浮点数除法带来的精度问题，我们使用乘法形式。这个条件告诉我们，对于任意两个物品，满足 $w_j \cdot c_i > w_i \cdot c_j$ 的物品 $i$ 应该排在物品 $j$ 的前面（更靠下）。

结论

因此，最优的贪心策略是：将所有物品按照 $w_j \cdot c_i > w_i \cdot c_j$ 规则进行排序，这等价于按 $c/w$ 的比值进行降序排序。排序后，从上到下依次计算每个物品的实际体积并求和。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

struct Item {
    int id;
    long long w, v, c;
};

bool compareItems(const Item& a, const Item& b) {
    // a应该在b下面
    // w_b * c_a > w_a * c_b
    return b.w * a.c > a.w * b.c;
}

int main() {
    int n;
    cin >> n;

    vector<Item> items(n);
    for (int i = 0; i < n; ++i) {
        items[i].id = i;
        cin >> items[i].w >> items[i].v >> items[i].c;
    }

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

    long long total_volume = 0;
    long long weight_above = 0;
    
    // 从上到下遍历
    for (int i = n - 1; i >= 0; --i) {
        total_volume += items[i].v - weight_above * items[i].c;
        weight_above += items[i].w;
    }

    cout << total_volume << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class Item {
        long w, v, c;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item();
            items[i].w = sc.nextLong();
            items[i].v = sc.nextLong();
            items[i].c = sc.nextLong();
        }

        Arrays.sort(items, (a, b) -> {
            // b.w * a.c > a.w * b.c
            long val = b.w * a.c - a.w * b.c;
            if (val > 0) return -1;
            if (val < 0) return 1;
            return 0;
        });

        long totalVolume = 0;
        long weightAbove = 0;
        
        // 从上到下遍历
        for (int i = n - 1; i >= 0; i--) {
            totalVolume += items[i].v - weightAbove * items[i].c;
            weightAbove += items[i].w;
        }

        System.out.println(totalVolume);
    }
}

import sys
from functools import cmp_to_key

class Item:
    def __init__(self, w, v, c):
        self.w = w
        self.v = v
        self.c = c

def compare_items(a, b):
    # b.w * a.c > a.w * b.c
    val = b.w * a.c - a.w * b.c
    if val > 0:
        return -1
    elif val < 0:
        return 1
    else:
        return 0

def solve():
    n = int(input())
    items = []
    for _ in range(n):
        w, v, c = map(int, input().split())
        items.append(Item(w, v, c))
    
    items.sort(key=cmp_to_key(compare_items))

    total_volume = 0
    weight_above = 0
    
    # 从上到下遍历
    for i in range(n - 1, -1, -1):
        total_volume += items[i].v - weight_above * items[i].c
        weight_above += items[i].w
        
    print(total_volume)

solve()

算法及复杂度

算法：贪心算法
时间复杂度： $O(N \log N)$
- 主要开销在于对 N 个物品进行排序。
空间复杂度： $O(N)$
- 用于存储 N 个物品的信息。