【GESP】C++三级练习 luogu-P2911 [USACO08OCT] Bovine Bones G

GESP C++三级练习，一维数组练习，难度★★✮☆☆。

luogu-P2911 [USACO08OCT] Bovine Bones G

题目要求

题目描述

Bessie 喜欢桌游和角色扮演游戏，所以她说服了 Farmer John 驾车送她去爱好商店，在那里她购买了三个用于掷骰子的骰子。这些公平的骰子分别有 $S_1$、$S_2$ 和 $S_3$ 个面（$2 \leq S_1 \leq 20$；$2 \leq S_2 \leq 20$；$2 \leq S_3 \leq 40$）。Bessie 不断地掷骰子，试图找出哪个三个骰子的和出现得最频繁。给定每个骰子的面数，确定哪个三个骰子的和出现得最频繁。如果有多个和出现得最频繁，报告其中最小的和。

输入格式

第 1 行：三个用空格分隔的整数：$S_1$、$S_2$ 和 $S_3$。

输出格式

第 1 行：当骰子以每种可能的组合掷出时，出现次数最多的最小整数和。

输入输出样例 #1

输入 #1

3 2 3

输出 #1

5

说明/提示

这里是所有可能的结果。

1 1 1 -> 3  
1 2 1 -> 4  
2 1 1 -> 4  
2 2 1 -> 5  
3 1 1 -> 5  
3 2 1 -> 6 
1 1 2 -> 4  
1 2 2 -> 5  
2 1 2 -> 5  
2 2 2 -> 6  
3 1 2 -> 6  
3 2 2 -> 7 
1 1 3 -> 5  
1 2 3 -> 6  
2 1 3 -> 6  
2 2 3 -> 7  
3 1 3 -> 7  
3 2 3 -> 8

5 和 6 都出现得最频繁（各五次），所以答案是 5。

---

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：
   • 掷三个不同面数的骰子，统计所有可能的点数和
   • 找出出现次数最多的和
   • 如果有多个和出现次数相同，取最小值
2. 解题关键：
   • 核心思路 - 模拟统计法：
     1. 使用数组记录每个可能的和出现的次数：
        • 创建一个足够大的数组result，下标表示和，值表示该和出现的次数
     2. 三重循环遍历所有可能的骰子点数组合：
        • 第一个骰子：1到s1
        • 第二个骰子：1到s2
        • 第三个骰子：1到s3
     3. 对每种组合，计算三个数的和并在result数组中对应位置加1
     4. 最后遍历result数组，找出出现次数最多的最小和
3. 复杂度分析：
   • 时间复杂度：$O(S_1 \times S_2 \times S_3)$，其中$S_1$、$S_2$、$S_3$分别为三个骰子的面数
   • 空间复杂度：$O(S_1 + S_2 + S_3)$，需要一个数组存储所有可能的和

---

示例代码

#include <iostream>

// 用于存储每个骰子点数和出现的次数
int result[100] = {0};
int main () {
    // 三个骰子的面数
    int s1, s2, s3;
    // 从标准输入读取三个骰子的面数
    std::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++) {
                // 统计每个和出现的次数
                result[i + j + k]++;
            }
        }
    }

    // 记录最大出现次数
    int max = 0;
    // 记录最大出现次数对应的和
    int max_idx = 0;
    // 遍历所有可能的和，找出出现次数最多的最小和
    for (int i = 0; i <= s1 + s2 + s3; i++) {
        if (result[i] > max) {
            max = result[i];
            max_idx = i;
        }
    }
    // 输出结果
    std::cout << max_idx;
    return 0;
}              

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助