「POI2007 R3」砝码 Weights 题解

题目分析

我们有 $n$ 个容器和 $m$ 个砝码：

• 每个容器有重量限制 $w_i$
• 每个砝码有重量 $m_i$
• 关键条件：任意两个砝码，其中一个的重量整除另一个的重量
• 目标：最大化能装进容器的砝码数量

关键性质

砝码之间的整除关系意味着所有砝码的重量可以表示为：

其中 $g$ 是最小砝码重量，$k_i$ 是正整数。

这说明：

1. 所有砝码重量都是最小砝码重量的倍数
2. 砝码重量之间形成一条整除链（或几条链，但任意两个砝码间都有整除关系）
3. 砝码可以按重量排序，小的砝码是大的砝码的约数

解题思路

由于砝码之间存在整除关系，我们可以采用策略：

1. 砝码排序：将砝码按重量从大到小排序
2. 容器管理：使用有序集合（如 multiset）存储可用容器容量
3. 匹配过程：对于每个砝码（从大到小），找到能容纳它的最小可用容器
   • 如果找到，使用该容器并移除它
   • 如果没找到，跳过该砝码

为什么这样可行？

• 大砝码优先：大砝码更难放置，所以优先处理
• 最小适用容器：将刚好能装下砝码的容器用于该砝码，保留大容器给后面可能更大的砝码
• 整除关系的优势：如果一个大砝码能放入容器，那么比它小的砝码（都是它的约数）也能放入同一容器

算法步骤

1. 读入 $n, m$
2. 读入容器容量 $w_i$ 并存入 multiset
3. 读入砝码重量 $m_i$ 并按从大到小排序
4. 遍历排序后的砝码：
   • 在容器集合中查找第一个 ≥ 当前砝码重量的容器
   • 如果找到，移除该容器，答案加1
5. 输出答案

复杂度分析

• 排序：$O(m \log m)$
• 每个砝码的查找操作：$O(\log n)$
• 总复杂度：$O(m \log m + m \log n)$，在 $n, m \leq 10^5$ 范围内可行

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    vector<long long> containers(n);
    for (int i = 0; i < n; i++) {
        cin >> containers[i];
    }
    
    vector<long long> weights(m);
    for (int i = 0; i < m; i++) {
        cin >> weights[i];
    }
    
    // 排序砝码（从大到小）
    sort(weights.begin(), weights.end(), greater<long long>());
    
    // 使用multiset管理可用容器
    multiset<long long> available(containers.begin(), containers.end());
    
    int count = 0;
    for (long long weight : weights) {
        // 找到能容纳当前砝码的最小容器
        auto it = available.lower_bound(weight);
        if (it != available.end()) {
            available.erase(it);
            count++;
        }
    }
    
    cout << count << "\n";
    return 0;
}

样例验证

输入：

2 4
13 9
4 12 2 4

处理过程：

• 砝码排序后：12, 4, 4, 2
• 可用容器：9, 13

步骤：

1. 砝码12 → 容器13（移除13），计数=1
2. 砝码4 → 容器9（移除9），计数=2
3. 砝码4 → 无合适容器，跳过
4. 砝码2 → 无合适容器，跳过

输出：2 ❌（但样例答案是3）

问题修正

上面的简单贪心在样例中得不到正确答案，说明问题更复杂。实际上，一个容器可以放多个砝码，我们需要考虑砝码的组合。

正确解法思路

1. 砝码体系分析：由于整除关系，所有砝码重量可以看作 $g \times 2^{a} \times 3^{b} \times \dots$ 的形式
2. 二进制表示：将容器容量和砝码重量都用最小砝码重量的倍数表示
3. 贪心填充：从大到小尝试砝码，对于每个砝码，尝试在所有容器中寻找能容纳它的位置，考虑砝码组合

由于一个容器可以放多个砝码，我们需要更复杂的匹配算法，可能涉及：

• 将容器容量按砝码基数的倍数分解
• 使用优先队列或更复杂的贪心匹配
• 或者转化为网络流问题（但数据规模较大）

本题的实际正解需要利用整除链的性质，将砝码按质因数分解的形式组织，然后用贪心+分解的方法求解。