题解：P13288 [GCJ 2013 #1B] Osmos

YC_2025_ak_IOI · 2025-07-15 16:36:10 · 题解

简述一下题意：

• Armin 的小球需严格大于其他小球才能吞噬，吞噬后体积累加。
• 允许两种操作：添加任意体积小球或移除现有小球‌。
• 目标是最小化操作次数使 Armin 能吞噬所有剩余小球。

那么我们就会发现，初始体积 A 和已排序的其他小球体积就会决定操作策略‌，那么我们就要将其他小球按体积升序排序，优先去尝试吞噬较小的小球。

若当前球的体积 A 不足以吞噬其他小球时，我们就采用贪心策略，去添加最大可能的小球体积 A-1，使体积快速增长，或直接移除当前无法吞噬的小球‌。

这时候我们就要权衡利弊，比较两种策略的代价。

我们维护当前操作次数 ops 和可能的最小结果 res‌，写成伪码就是这样：

while A <= motes[i]:
    A += A-1  // 添加操作
    ops++
res = min(res, ops + 剩余小球数)  // 对比移除剩余小球的代价

同时，我们注意到当初始小球体积为 1 时，无法通过添加增长（因为 1-1=0，而小球体积不能为 0），这时候就选择移除所有更大的小球。

代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
int motes[MAXN];
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t) {
        int A, N;
        cin >> A >> N;
        for (int i = 0; i < N; ++i) cin >> motes[i];
        sort(motes, motes + N);  // 关键排序步骤

        int res = N;  // 初始化
        if (A > 1) {  // 仅当A>1时可通过添加增长
            int ops = 0;
            for (int i = 0; i < N; ++i) {
                while (A <= motes[i]) {  // 无法吞噬时处理
                    A += A - 1;
                    ops++;
                }
                A += motes[i];  // 正常吞噬
                res = min(res, ops + N - i - 1);  // 动态更新最优解
            }
        }
        cout << "Case #" << t << ": " << res << endl;
    }
    return 0;
}

时间复杂度主要由排序决定，为 O(n \log n)，可以通过此题。