1. PAT乙级1092题解：找出最受欢迎的月饼口味

这道题目来自PAT乙级考试的1092题，主要考察数组的基本操作和简单的统计计算。题目背景设定在一个月饼销售场景，要求我们统计每种口味的月饼总销量，并找出最受欢迎的口味。

1.1 题目理解与需求分析

题目大意是：有N种不同口味的月饼，M家门店参与了销售统计。每家门店都会上报每种口味的销售数量。我们需要：

1. 计算每种口味在所有门店的总销量
2. 找出销量最高的那个数值
3. 输出这个最高销量值
4. 输出所有达到这个销量的口味编号（按输入顺序）

输入格式：

• 第一行两个整数N和M（1≤N,M≤1000）
• 接下来M行，每行N个整数，表示该门店各口味的销量

输出格式：

• 第一行输出最大销量值
• 第二行输出所有达到最大销量的口味编号（按输入顺序，空格分隔）

1.2 解题思路与算法选择

这道题的核心在于：

1. 累加统计：我们需要对每种口味在各个门店的销量进行累加
2. 找最大值：在所有累加结果中找出最大的那个值
3. 输出结果：按要求格式输出最大值和对应的口味编号

选择的数据结构：

• 使用一个大小为N+1的数组（或vector）来存储每种口味的累计销量
• 数组索引直接对应口味编号（1-based）

算法复杂度：

• 时间复杂度：O(M×N)，因为需要遍历所有门店的所有口味
• 空间复杂度：O(N)，只需要存储各口味的累计销量

2. 代码实现详解

2.1 基础框架与输入处理

#include<bits/stdc++.h> using namespace std; int main() { int n, m, num; cin >> n >> m; vector<int> v(n + 1);

这部分代码做了以下工作：

1. 包含常用头文件<bits/stdc++.h>（竞赛常用，实际工程不推荐）
2. 使用标准命名空间std
3. 定义主函数
4. 读取两个整数n（口味数量）和m（门店数量）
5. 创建大小为n+1的vector（索引1-n对应各口味）

注意：这里使用n+1是为了让下标直接对应口味编号（1-based），避免0号元素的混淆。

2.2 数据累加处理

for(int i = 0; i < m; i++) { for(int j = 1; j <= n; j++) { cin >> num; v[j] += num; } }

这段代码实现了：

1. 外层循环遍历所有m家门店
2. 内层循环遍历所有n种口味
3. 读取当前门店当前口味的销量num
4. 将该销量累加到对应口味的累计和中

技巧：使用+=运算符直接累加，避免了额外的中间变量。

2.3 找出最大值

int maxnum = -1; for(int i = 1; i <= n; i++) maxnum = max(maxnum, v[i]); cout << maxnum << endl;

这部分逻辑：

1. 初始化maxnum为-1（确保任何销量都会大于它）
2. 遍历所有口味，使用max函数更新最大值
3. 输出找到的最大值

注意：maxnum初始值设为-1是安全的，因为题目保证销量是非负整数。

2.4 输出最大销量口味编号

int flag = 0; for(int i = 1; i <= n; i++) if(v[i] == maxnum) { if(flag == 1) cout << " "; flag = 1; cout << i; }

这段代码处理了：

1. 使用flag标记是否是第一个输出的编号
2. 遍历所有口味，检查是否等于最大值
3. 如果是第一个输出的编号，不输出前导空格
4. 后续编号前都输出一个空格
5. 直接输出口味编号i

技巧：使用flag控制空格输出，避免了末尾多余空格的问题。

3. 代码优化与注意事项

3.1 边界情况处理

虽然题目给出了数据范围，但实际编码时应考虑：

1. 当n=1时的特殊情况
2. 所有口味销量相同的情况
3. 最大销量为0的情况（虽然题目没说是否可能）

3.2 输入输出优化

对于大规模数据（虽然本题n,m≤1000）：

1. 可以使用更快的输入方式（如scanf代替cin）
2. 关闭同步流：ios::sync_with_stdio(false);

优化后的输入部分：

ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m;

3.3 变量命名建议

原代码使用v作为数组名不够直观，可以改为：

vector<int> totalSales(n + 1);

其他变量也可以更具描述性：

• num → currentSale
• maxnum → maxSales
• flag → isFirstOutput

4. 常见问题与调试技巧

4.1 易错点分析

1. 数组大小错误：忘记是n+1导致越界
2. 索引错误：使用0-based还是1-based要统一
3. 空格控制：最后一个编号后不能有多余空格
4. 初始化问题：maxnum初始值不够小可能导致错误

4.2 测试用例设计

建议测试以下情况：

1. 常规情况：

3 2 1 2 3 4 5 6

输出应为：

9 3

2. 多个最大销量：

4 3 1 2 3 4 4 3 2 1 1 1 1 1

输出应为：

6 1 2

3. 边界情况：

1 1 100

输出应为：

100 1

4.3 调试技巧

1. 打印中间结果：在累加后打印v数组检查
2. 使用小数据测试：先验证简单情况
3. 检查循环边界：特别是从1开始还是0开始
4. 使用调试器：单步执行观察变量变化

5. 算法扩展与变种思考

5.1 类似问题

1. 找出销量前k名的口味
2. 计算每种口味的平均销量
3. 找出销量超过某个阈值的口味

5.2 性能优化

如果数据量很大（如n,m=1e5）：

1. 可以使用并行计算处理不同门店的数据
2. 考虑使用更高效的数据结构
3. 分批处理输入数据

5.3 实际应用扩展

这种累加统计模式可以应用于：

1. 电商商品销量统计
2. 用户行为分析
3. 多维度数据聚合

在实际项目中，类似的统计需求很常见，掌握这种基础模式非常重要。我建议初学者不仅要能写出正确代码，还要理解每个步骤的意义和可能的变种，这样才能真正掌握算法思想。