Move - 题解

标签与难度

标签: 二分答案, 贪心, 模拟, multiset, 数据结构, Greedy, Binary Search on Answer 难度: 1600

题目大意喵~

你好呀，未来的算法大师！这道题是关于一个叫 TangTang 的同学搬家的故事，喵~

TangTang 有 n 件物品，每件物品都有一个体积 $v_i$ 。他需要把这些物品全部装进最多 k 个箱子里。所有的箱子都拥有相同的、待我们确定的体积 V。

最关键的是 TangTang 的装箱策略，一定要仔细看哦：

他会一个一个地装箱子。先把一个箱子尽可能装满，再去装下一个。
对于每个箱子，他会反复地从 所有还没被装箱的物品 中，挑选出体积 最大且能放进箱子当前剩余空间 的那一件，然后放进去。这个过程会一直重复，直到这个箱子再也放不下任何一件未装箱的物品为止。

我们的任务就是，找到一个最小的箱子体积 V，使得 TangTang 能用他的策略把所有 n 件物品都装进 k 个箱子里。

简单来说，就是求满足特定贪心装箱策略的最小箱子体积，的说！

解题思路分析

喵哈哈，看到“最小的...值”这种问法，我的猫猫直觉就告诉我，这很可能是一道 二分答案 的题目！你想想看，是不是有这个感觉呐？

我们来分析一下为什么可以用二分答案。假设我们随便猜一个箱子的体积 V。

如果这个体积 V 的箱子，能够成功装下所有物品，那么任何比 V 更大的体积 V'（比如 V+1）肯定也足够装下所有物品，对吧？因为空间只增不减，原来的装法肯定依然适用。
反过来，如果体积 V 的箱子装不下所有物品，那么任何比 V 更小的体积 V''（比如 V-1）肯定也装不下。因为空间更小了，原来都装不下，现在更不可能了。

这种性质叫做 单调性！就像一排猫粮碗，左边的吃不饱，右边的肯定能吃饱，我们要找的就是最左边那个刚好能吃饱的碗！这不就是二分查找最擅长解决的问题嘛？

所以，我们的整体思路就清晰了：

确定二分范围：我们需要为箱子的体积 V 确定一个搜索的下界 left 和上界 right。
- left：箱子的体积至少要能装下体积最大的那件物品吧？不然最大的那件物品永远也装不进去。所以，left 的初始值就是所有物品体积中的最大值 max_v。
- right：一个绝对安全的上界就是所有物品的体积总和 sum_v。想象一下，如果 k=1，那箱子体积就必须是 sum_v 才能装下所有东西。这是一个肯定可行的解。
二分查找：在 [left, right] 这个区间内进行二分查找。每次取中间值 mid 作为箱子的候选体积。
编写 check(V) 函数：这是最核心的一步！我们需要一个函数来判断，当箱子体积为 V 时，能否用题目的策略装下所有物品。如果可以，返回 true；否则返回 false。
更新二分区间：
- 如果 check(mid) 返回 true，说明体积 mid 是可行的。但我们想找的是最小体积，所以 mid 可能不是最优解，真正的答案可能更小。于是我们记录下这个可行的答案，并尝试在左半部分继续寻找：ans = mid, right = mid - 1。
- 如果 check(mid) 返回 false，说明体积 mid 太小了，不够用。我们必须增大箱子体积，所以需要在右半部分寻找：left = mid + 1。

如何实现 check(V) 函数呢？

这个函数需要精确地模拟 TangTang 的装箱过程。题目说：“对于每个箱子，他会反复地从所有还没被装箱的物品中，挑选出体积最大且能放进箱子当前剩余空间的那一件”。

这句话是关键！我们需要一个数据结构，能够高效地完成以下操作：

存储所有未装箱的物品。
快速找到小于等于某个值（箱子剩余容量）的最大的物品。
方便地移除被装箱的物品。

std::multiset 简直是为这个需求量身定做的喵！multiset 是一个有序的集合（允许有重复元素），查找和删除操作的效率都很高（对数时间复杂度）。

check(V) 的模拟步骤如下：

把所有 n 个物品的体积都放进一个 multiset 里。
循环 k 次，代表我们有 k 个箱子。
在每次循环中，模拟装一个箱子：
- 设置当前箱子的剩余容量 currentCapacity = V。
- 进入一个内部循环，只要箱子还有容量，并且还有物品没装：
  - 在 multiset 中查找小于等于 currentCapacity 的最大元素。这可以用 multiset.upper_bound(currentCapacity) 实现。这个函数会返回第一个大于 currentCapacity 的元素的迭代器。我们只需要将这个迭代器减一，就指向了我们想要的那个“最大且能放入”的物品啦！
  - 如果 upper_bound 返回的是 multiset.begin()，说明所有剩下的物品都比当前箱子的剩余容量要大，这个箱子装不下了，跳出内循环。
  - 否则，我们找到了一个可以装的物品。从 currentCapacity 中减去它的体积，并从 multiset 中移除它。
当 k 个箱子都装完后，检查 multiset 是否为空。如果为空，说明所有物品都被成功装箱，返回 true。否则，返回 false。

这样，整个解题思路就完整啦！是不是很清晰呢，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，注释超详细的哦！

cpp

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

// 检查函数，判断给定箱子容量 boxCapacity 是否足够装下所有物品
// n: 物品数量, k: 箱子数量
// items: 存储所有物品体积的向量
// boxCapacity: 当前尝试的箱子容量
bool check(int k, const std::vector<int>& items, long long boxCapacity) {
    // 使用 multiset 来高效地管理未装箱的物品
    // multiset 会自动排序，并允许我们快速找到和删除元素
    std::multiset<int> unpackedItems(items.begin(), items.end());

    // 我们有 k 个箱子可以使用
    for (int i = 0; i < k; ++i) {
        // 如果所有物品都装完了，就提前结束，说明容量是足够的
        if (unpackedItems.empty()) {
            break;
        }

        long long currentBoxSpace = boxCapacity; // 当前箱子的剩余空间

        // 只要箱子还有空间，并且还有物品未装，就继续尝试装箱
        while (currentBoxSpace > 0 && !unpackedItems.empty()) {
            // 寻找体积不大于箱子剩余空间的、最大的物品
            // upper_bound(x) 返回第一个 > x 的元素的迭代器
            auto it = unpackedItems.upper_bound(currentBoxSpace);

            // 如果 upper_bound 返回的是 begin()，说明 multiset 中所有物品的体积
            // 都比 currentBoxSpace 大，这个箱子再也装不下任何东西了
            if (it == unpackedItems.begin()) {
                break; // 结束当前箱子的装填
            }

            // 回退一个位置，it 现在指向的就是 <= currentBoxSpace 的最大元素
            --it;

            int itemVolume = *it; // 获取这个物品的体积
            currentBoxSpace -= itemVolume; // 减去占用的空间
            unpackedItems.erase(it); // 从 multiset 中移除这个已装箱的物品
        }
    }

    // 如果 k 个箱子用完后，所有物品都被装箱（multiset 为空），则此容量可行
    return unpackedItems.empty();
}

void solve(int caseNum) {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> items(n);
    long long sumVolume = 0;
    int maxVolume = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> items[i];
        sumVolume += items[i];
        if (items[i] > maxVolume) {
            maxVolume = items[i];
        }
    }

    // 二分答案的搜索范围
    long long left = maxVolume; // 下界：箱子至少要能装下最大的物品
    long long right = sumVolume; // 上界：一个箱子装所有物品，肯定够
    long long ans = right;       // 存储最终答案，初始化为一个肯定可行的值

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        if (check(k, items, mid)) {
            // 如果 mid 容量可行，说明它是一个潜在的答案
            // 我们尝试寻找更小的可行容量
            ans = mid;
            right = mid - 1;
        } else {
            // 如果 mid 容量不可行，说明箱子太小了，需要增大容量
            left = mid + 1;
        }
    }

    std::cout << "Case #" << caseNum << ": " << ans << std::endl;
}

int main() {
    // 提高C++ IO效率，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N \cdot \log(\text{SumV}))$
- 我们的二分查找会在一个范围大约为 sumVolume 的区间内进行，所以二分部分的复杂度是 $O(\log(\text{SumV}))$ 。
- check 函数是复杂度的主要来源。在 check 函数内部：
  - 初始化 multiset 需要将 N 个元素插入，复杂度为 $O(N \log N)$ 。
  - 之后，每个物品最多被查找 (upper_bound) 一次和删除 (erase) 一次。这两步操作在 multiset 中的复杂度都是 $O(\log N)$ 。所以处理所有 N 个物品的总复杂度是 $O(N \log N)$ 。
- 因此，总的时间复杂度就是二分次数乘以 check 函数的复杂度，即 $O(\log(\text{SumV}) \cdot N \log N)$ 。
空间复杂度: $O(N)$
- 我们需要一个 std::vector 来存储输入的 n 个物品的体积，这占用了 $O(N)$ 的空间。
- 在 check 函数中，我们创建了一个 std::multiset，它最多也存储 n 个物品，同样占用 $O(N)$ 的空间。
- 所以，总的额外空间复杂度是 $O(N)$ ，的说。

知识点总结

这道题真是一道非常经典的复合型题目，能让我们学到很多东西呢！

二分答案 (Binary Search on Answer): 这是解决“求满足条件的最小值/最大值”问题的强大模板。关键在于识别问题的单调性。
贪心 (Greedy Algorithm): 题目本身就定义了一种贪心策略（每次装能装下的最大物品）。我们的任务是模拟它，而不是设计新的贪心策略。
模拟 (Simulation): check 函数的核心就是对题目描述的装箱过程进行精确的模拟。
std::multiset 的妙用: multiset 在这里是实现模拟的关键数据结构。它能自动维护元素的有序性，并提供高效的 upper_bound 和 erase 操作，完美契合了“找到小于等于X的最大值”并移除的需求。

希望这篇题解能帮助你更好地理解这道题，如果还有不懂的地方，随时可以再来问我哦，喵~ >w<

Move - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​