#5457. 「ROI 2012 Day 1」杏干 题解

问题分析

我们有 $N$ 枚金币，其中恰好一枚是较轻的假币。使用魔法天平：

• 如果两边重量相同，消耗 $R$ 个杏干
• 如果两边重量不同，消耗 $U$ 个杏干，并知道哪边轻

目标：在最坏情况下保证找出假币，且最小化杏干消耗。

关键观察

1. 信息论下界：每次称量最多获得 $\log_2 3$ 比特信息（因为结果有3种：左轻、右轻、相等）
2. 决策树模型：这是一个构建最优决策树的问题，叶子数 $\geq N$（每个金币对应一个叶子）
3. 状态表示：设 $f(k)$ = 用最优策略在 $k$ 个金币中找假币的最小最坏代价

动态规划解法

状态转移

假设我们有 $n$ 个待检测金币。一次称量时：

• 左边放 $a$ 个，右边放 $a$ 个（$1 \leq a \leq \lfloor n/2 \rfloor$）
• 剩下 $n-2a$ 个不参与本次称量

三种结果：

1. 左边轻：假币在左边 $a$ 个中，代价 $U + f(a)$
2. 右边轻：假币在右边 $a$ 个中，代价 $U + f(a)$
3. 两边相等：假币在未称的 $n-2a$ 个中，代价 $R + f(n-2a)$

最坏情况代价：

$$f(n) = \min_{1 \leq a \leq \lfloor n/2 \rfloor} \max(U + f(a), R + f(n-2a)) $$

边界条件

• $f(0) = 0$（没有金币）
• $f(1) = 0$（只剩一个金币，必然是假币）

算法优化

直接DP复杂度 $O(N^2)$ 太高，需要优化。

观察单调性

令 $g(a) = \max(U + f(a), R + f(n-2a))$：

• $U + f(a)$ 随 $a$ 增加而增加
• $R + f(n-2a)$ 随 $a$ 增加而减少

最优的 $a$ 在两者交点附近，可以三分查找。

更高效的实现

由于 $N$ 很大，我们利用决策的规律性：

• 最优的 $a$ 通常接近 $n/3$
• 可以只检查 $a$ 在 $[n/3-c, n/3+c]$ 范围内的值（$c$ 为小常数）

代码实现

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

const int MAXN = 1000005;

long long f[MAXN];
int N, R, U;

long long cost(int a, int n) {
    return max(1LL * U + f[a], 1LL * R + f[n - 2 * a]);
}

int main() {
    cin >> N >> R >> U;
    
    f[0] = f[1] = 0;
    
    for (int n = 2; n <= N; n++) {
        long long best = 1LL << 60;
        
        // 在 n/3 附近搜索最优的 a
        int left = max(1, n / 3 - 2);
        int right = min(n / 2, n / 3 + 2);
        
        for (int a = left; a <= right; a++) {
            best = min(best, cost(a, n));
        }
        
        // 检查边界情况
        if (n / 3 - 2 > 1) {
            best = min(best, cost(1, n));
        }
        if (n / 3 + 2 < n / 2) {
            best = min(best, cost(n / 2, n));
        }
        
        f[n] = best;
    }
    
    cout << f[N] << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$，每个 $n$ 只检查常数个 $a$ 值
• 空间复杂度：$O(N)$