算法之美：从暴力枚举到 O(1) 的概率论降维打击

—— 洛谷 P2911 [USACO08OCT] Bovine Bones G 数学解法详解

在算法竞赛中，求多个独立随机变量的和的分布是一个非常经典的模型。本题要求解的是：投掷三个面数分别为 A, B, C 的骰子，求出现概率（频次）最高的和；若有并列，取最小的那个。

虽然 O(ABC) 的暴力做法足以 AC，但我们今天来探讨它背后的纯数学规律，推导出一个时间复杂度为 O(1) 的终极公式。

一、降维思考：两个骰子的和 (A + B)

为了方便推导，我们先假设三个骰子的面数从小到大排序为 A \leq B \leq C （即 C 最大）。

我们先只看前两个骰子（面数分别为 A 和 B）。设它们的点数为 x 和 y。令 s = x + y，那么 s 的频次分布（概率质量函数）长什么样呢？

因为它们是均匀分布的离散变量，它们的卷积（即和的分布）会呈现出一个等腰梯形（如果 A = B，则退化为等腰三角形）：

上升期：当和 s 从 2 增长到 A + 1 时，组合数从 1 线性递增到 A。
平顶期（Plateau）：当 s 在 A + 1 到 B + 1 之间时，组合数保持在最大值 A 不变。
下降期：当 s 从 B + 1 增长到 A + B 时，组合数线性递减回 1。

小结：前两个骰子的和 s = A + B，其分布是一个底边长为 A + B - 1，最高频次段落在 [A + 1, B + 1] 的梯形。

二、引入第三个骰子：滑动窗口的魔法

现在我们加入第三个骰子 C，求总和 T = x + y + z。从数学上看，这等价于用一个宽度为 C 的滑动窗口，去对前面那个“梯形分布”求区间和。

因为 C 是最大的骰子（C \geq B \geq A），此时会发生两种截然不同的情况，这也是公式分段的核心：

情况 1：当 C \geq A + B - 1 时（大窗口）

此时第三个骰子的面数非常大，导致滑动窗口的宽度 大过了整个梯形底边的总宽度 (A + B - 1)。这意味着，在滑动的某一段过程中，窗口可以完全框住整个梯形！

一旦梯形被完全框住，所有 A \times B 种组合都被纳入了计算，频次达到了绝对的理论上限。
这个“全覆盖”状态会持续一段时间，形成一个新的、更宽的平顶期。
这个终极平顶期的范围是 [A + B + 1, C + 2]。
题目要求频次最高时取最小的和，因此答案直接锁定为区间的左端点：A + B + 1。

情况 2：当 C < A + B - 1 时（小窗口）

此时滑动窗口比梯形的底边要窄，它无法一次性框住整个梯形。

由于梯形是对称且“中间高两边低”的，滑动窗口的和要在哪里达到最大呢？显然是窗口正对准梯形正中心的时候！
此时总和分布是一个完美对称的“钟形”类正态分布，没有宽广的平顶，最高点仅在分布的 期望值（均值） 处取得。
均值 \mu 的计算非常简单：

\mu = \frac{(A + 1)}{2} + \frac{(B + 1)}{2} + \frac{(C + 1)}{2} = \frac{A + B + C + 3}{2}

注意：如果分子是偶数，均值是整数，这是唯一的峰值；如果分子是奇数，均值是“点五”（如 5.5），说明峰值由均值两侧的两个整数（5 和 6）共享。题目要求取最小的，因此我们对均值向下取整即可。
答案：\left\lfloor \frac{A + B + C + 3}{2} \right\rfloor。

三、终极 O(1) 公式总结

通过上述概率论的卷积分析，我们将 O(ABC) 的暴力算法压缩成了几行极其优雅的数学逻辑：

将输入的三个面数 A, B, C 升序排序，得到 A \leq B \leq C （保证 C 最大）。
判断最大的面数 C 与前两个面数之和 A + B 的关系：
- 若 C \geq A + B - 1：输出 A + B + 1
- 若 C < A + B - 1：输出 (A + B + C + 3) / 2 (整型除法自带向下取整)

验证案例

假设掷出 3 个面的骰子、2 个面的骰子、3 个面的骰子（即 3 2 3）。

排序后：A=2, B=3, C=3。
判断条件：A + B - 1 = 4，而 C = 3。满足 C < A + B - 1 (情况 2)。
代入公式：(2 + 3 + 3 + 3) / 2 = 11 / 2 = 5（整型除法）。
正确答案即为 5。这与暴力打表的结果完美契合。

数学，就是算法中最锐利的剑！

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 优化标准输入输出
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    vector<int> s(3);
    if (cin >> s[0] >> s[1] >> s[2]) {
        // 步骤 1：排序，使得 s[0] <= s[1] <= s[2] (对应推导中的 A <= B <= C)
        sort(s.begin(), s.end());

        int A = s[0];
        int B = s[1];
        int C = s[2];

        // 步骤 2：应用概率论推导出的 O(1) 分段函数
        if (C >= A + B) {
            // 滑动窗口大过底层梯形，最大概率产生平顶，取最左端
            cout << A + B + 1 << "\n";
        } else {
            // 滑动窗口较小，最大概率出现在正中心均值处（如果有两个峰，整数除法自动向下取整拿到最小值）
            cout << (A + B + C + 3) / 2 << "\n";
        }
    }

    return 0;
}

Hotkeys

菜单

分享

算法之美：从暴力枚举到 O(1) 的概率论降维打击