P2911题解

· · 题解

题目大意

这道题说的是有3个骰子，求出这3个骰子的点数和出现次数最多的数。

样例描述

先枚举所有情况，再看和出现次数最多的数，答案是5。

解题思路

先分析一下时间复杂度，2≤S1​≤20；2≤S2​≤20；2≤S3​≤40。 所以时间复杂度为O(S1*S2*S3)。

我们可以先枚举每个骰子的点数，让后放到一个桶里，用 maxid 来记录每个点数出现的次数。

代码思路

先开一个桶数组 t 。 t[i] 表示点数和为 i 的骰子出现的次数，用 maxid 保存出现次数最多的下标，最后输出 maxid 。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=20+20+40+5;
int a[N];//桶数组
int maxid=0;//最大值下标
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    int s1,s2,s3;
    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++){
                a[i+j+k]++;
                if(a[i+j+k]>a[maxid]) maxid=i+j+k;//统计
            }
        }
    }
    cout<<maxid;//输出
    return 0;
}