自动搬运

查看原文

来自洛谷，原作者为

	2011hym 暴力占据大脑，打表代替思考 | 寒鸦栖枯地，拿分靠暴力 | 空山不见人，爆0就红温

搬运于2025-08-24 21:43:21，当前版本为作者最后更新于2025-06-05 22:07:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验。

题解区的思路大都是暴力枚举，看完后我突然想起来有一个 $O(1)$ 的做法。

我有一计！

题目分析

找出三个骰子所有可能的和中出现次数最高的那个，如果有多个和出现次数相同，则输出字典序最小的那个。

解决思路

我们可以通过分析骰子面数之间的关系，直接计算最可能出现的和，而不需要枚举所有可能的组合。

三个骰子的和最可能出现在中间区域，具体位置取决于三个骰子面数的相对大小。

数学原理

本题解的知识点牵扯到概率论，读者自重。

这玩意基于概率分布的性质：

• 三个独立均匀分布的离散随机变量之和的概率分布呈近似正态分布。
• 当最小两个骰子的面数之和不超过最大骰子面数加 $1$ 时，峰值出现在 $1+b+c$。
• 否则峰值出现在更复杂的位置，由给定公式计算。

读者若想了解，可以在 OI Wiki 上搜索。

代码实现

这里提供两种做法。

$O(1)$ 做法：

#include <bits/stdc++.h>
using namespace std;
int a,b,c;
int main() {
    cin>>a>>b>>c;
    // 排序使 a>=b>=c。
    if(a<b)swap(a,b);
    if(b<c)swap(b,c);
    if(a<b)swap(a,b);
    if(b<=a-c+1){
        cout<<1+b+c;
    }else{
        cout<<2+a+(b-a+c-1)/2;
    }
    return 0;
}

$O(n^3)$ 做法：

#include <bits/stdc++.h>
using namespace std;
int freq[110],ans,cnt,s1,s2,s3;//统计和出现的频率。
int main() {
    cin>>s1>>s2>>s3;
    //枚举所有可能的骰子组。
    for(int i=1;i<=s1;i++){
        for(int j=1;j<=s2;j++){
            for(int k=1;k<=s3;k++){
                int sum=i+j+k;
                freq[sum]++;
            }
        }
    }
    //找出出现频率最高的最小和。
    for(int sum=3;sum<=s1+s2+s3;sum++){
        if(freq[sum]>cnt){
            cnt=freq[sum];
            ans=sum;
        }
    }
    cout<<ans;
    return 0;
}

update：2025.7.22 修正了两处小错误。