2679. 「BalticOI 2010」箱子 bins 题解

问题分析

有 $N$ 个箱子排成一行，大小分别为 $A_1, A_2, \ldots, A_N$。

操作规则：

1. 只能把左边的箱子放入右边的箱子中
2. 每个箱子最多装一个箱子，且必须是空的
3. 放入的箱子必须比外面的箱子小（严格小于）

目标： 找到最大的 $K$，使得前 $K$ 个箱子可以放入接下来的 $K$ 个箱子中（即箱子 $1..K$ 放入箱子 $K+1..2K$ 中）。

约束：

• 每个箱子只能使用一次（要么作为内箱被放入，要么作为外箱装入内箱）
• 匹配必须是一一对应的：每个内箱对应一个外箱
• 大小关系：内箱大小 < 外箱大小

关键观察

1. 问题转化

这本质上是一个二分图匹配问题：

• 左部：前 $K$ 个箱子（内箱）
• 右部：接下来的 $K$ 个箱子（外箱）
• 匹配条件：左箱大小 < 右箱大小

2. 单调性

如果 $K$ 可行，那么比 $K$ 小的值也一定可行（可以只使用部分匹配）。

因此我们可以二分答案：

• 左边界：$L = 0$
• 右边界：$R = \lfloor N/2 \rfloor$
• 检查每个 $mid$ 是否可行

算法思路

1. 二分框架

int L = 0, R = N/2;
while (L < R) {
    int mid = (L + R + 1) / 2;
    if (check(mid)) {
        L = mid;
    } else {
        R = mid - 1;
    }
}
cout << L << endl;

2. 检查函数 check(K)

给定 $K$，判断前 $K$ 个箱子能否放入第 $K+1$ 到 $2K$ 个箱子中。

贪心策略：

1. 将前 $K$ 个箱子（内箱）按大小从小到大排序
2. 将接下来的 $K$ 个箱子（外箱）按大小从小到大排序
3. 使用双指针匹配：
   • 遍历内箱（从小到大）
   • 对于每个内箱，找到最小的能容纳它的外箱

为什么贪心正确？

• 内箱从小到大：优先匹配小的内箱，给大的内箱留出更大的外箱
• 外箱从小到大：总是使用最小的可用外箱，最大化匹配机会

3. 检查函数实现

bool check(int K) {
    if (2*K > N) return false;
    
    // 复制前K个箱子（内箱）
    vector<int> inner(A.begin(), A.begin() + K);
    // 复制接下来K个箱子（外箱）
    vector<int> outer(A.begin() + K, A.begin() + 2*K);
    
    // 排序
    sort(inner.begin(), inner.end());
    sort(outer.begin(), outer.end());
    
    // 贪心匹配
    int i = 0, j = 0;  // i: 内箱指针, j: 外箱指针
    while (i < K && j < K) {
        if (inner[i] < outer[j]) {
            // 可以放入
            i++;
            j++;
        } else {
            // 当前外箱太小，尝试下一个外箱
            j++;
        }
    }
    
    return i == K;  // 所有内箱都匹配成功
}

复杂度分析

时间复杂度

• 二分：$O(\log N)$ 次
• 每次检查：
  • 复制数组：$O(K)$
  • 排序：$O(K \log K)$
  • 匹配：$O(K)$
• 总复杂度：$O(N \log N \log N) = O(N \log^2 N)$

对于 $N \le 20000$，这是可行的。

空间复杂度

• $O(K)$ 存储临时数组

优化

1. 避免多次排序

我们可以预处理整个数组，但每次检查需要不同的 $K$ 值段。由于 $K$ 变化，需要重新排序。

2. 使用计数排序

由于 $M \le 1000$ 较小，可以使用计数排序，将排序复杂度从 $O(K \log K)$ 降到 $O(K + M)$。

vector<int> count_sort(const vector<int>& arr, int M) {
    vector<int> count(M + 1, 0);
    for (int x : arr) {
        count[x]++;
    }
    
    vector<int> sorted;
    for (int val = 1; val <= M; val++) {
        for (int i = 0; i < count[val]; i++) {
            sorted.push_back(val);
        }
    }
    return sorted;
}

完整代码

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

int main() {
    int M, N;
    cin >> M >> N;
    
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    // 二分答案
    int L = 0, R = N / 2;
    int ans = 0;
    
    while (L <= R) {
        int K = (L + R) / 2;
        
        // 检查K是否可行
        if (2 * K > N) {
            R = K - 1;
            continue;
        }
        
        // 使用计数排序
        vector<int> count_inner(M + 1, 0);
        vector<int> count_outer(M + 1, 0);
        
        // 统计前K个箱子
        for (int i = 0; i < K; i++) {
            count_inner[A[i]]++;
        }
        // 统计接下来的K个箱子
        for (int i = K; i < 2 * K; i++) {
            count_outer[A[i]]++;
        }
        
        // 贪心匹配
        bool ok = true;
        int inner_ptr = 1, outer_ptr = 1;
        
        while (inner_ptr <= M && outer_ptr <= M) {
            // 跳过没有内箱的值
            while (inner_ptr <= M && count_inner[inner_ptr] == 0) inner_ptr++;
            // 跳过没有外箱的值
            while (outer_ptr <= M && count_outer[outer_ptr] == 0) outer_ptr++;
            
            if (inner_ptr > M) break;  // 所有内箱都匹配完了
            if (outer_ptr > M) {       // 还有内箱但没外箱了
                ok = false;
                break;
            }
            
            if (inner_ptr < outer_ptr) {
                // 当前内箱可以放入当前外箱
                // 匹配一对
                count_inner[inner_ptr]--;
                count_outer[outer_ptr]--;
            } else {
                // 当前外箱太小，尝试下一个外箱
                outer_ptr++;
            }
        }
        
        if (ok) {
            // 检查是否还有剩余内箱
            for (int i = 1; i <= M; i++) {
                if (count_inner[i] > 0) {
                    ok = false;
                    break;
                }
            }
        }
        
        if (ok) {
            ans = K;
            L = K + 1;
        } else {
            R = K - 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}

正确性证明

1. 贪心策略的正确性

我们使用经典的最小外箱匹配最小内箱策略：

• 将内箱和外箱都从小到大排序
• 对于每个内箱，使用最小的能容纳它的外箱

证明： 假设存在最优匹配，其中某个内箱 $a$ 没有使用最小的可用外箱 $b$，而是使用了更大的外箱 $c$，而 $b$ 匹配了更大的内箱 $d$。 我们可以交换：让 $a$ 匹配 $b$，$d$ 匹配 $c$。 由于 $a < b \le c$ 且 $d \le c$，交换后仍然合法，且不会使匹配变差。 因此贪心策略可以得到最优匹配。

2. 二分答案的正确性

如果 $K$ 可行，那么对于任意 $K' < K$，只需使用前 $K'$ 个匹配即可，所以 $K'$ 也一定可行。因此可行性具有单调性，可以使用二分。

示例验证

样例

5 10
2 2 1 4 3 2 5 4 2 3

• 检查 $K=4$： 内箱：前4个 [2,2,1,4] → 排序后 [1,2,2,4] 外箱：接下来4个 [3,2,5,4] → 排序后 [2,3,4,5] 匹配：

  • 1 < 2 ✓
  • 2 < 3 ✓
  • 2 < 4 ✓
  • 4 < 5 ✓ 全部匹配成功，$K=4$ 可行

• 检查 $K=5$： 内箱：前5个 [2,2,1,4,3] → 排序后 [1,2,2,3,4] 外箱：接下来5个 [2,5,4,2,3] → 排序后 [2,2,3,4,5] 匹配：

  • 1 < 2 ✓
  • 2 < 2 ✗（需要严格小于） 匹配失败，$K=5$ 不可行

所以最大 $K=4$，与样例输出一致。

总结

本题的关键：

1. 问题转化：将物理操作转化为二分图匹配问题
2. 单调性：可行性关于 $K$ 单调，可以使用二分
3. 贪心匹配：排序后双指针匹配
4. 优化：使用计数排序处理小范围值

算法复杂度 $O(N \log^2 N)$ 或优化后 $O(N \log N)$，对于 $N \le 20000$ 完全可行。