题解
运气最好的人
1 条题解
-
0
解题思路
编号 j 的人负责摘第 j 列,所以他摘到的花生总数 = 这一列所有元素的和。
做法是:先把 m 行 n 列的花生地逐行读进二维数组 a,再一列一列地求和: 用变量 mx 记录目前遇到的最大和,用变量 who 记录这个最大和对应的人(也就是列)编号。 如果某一列的和比 mx 大,就更新 mx 和 who。最后 who 就是运气最好的人,mx 就是他摘到的花生数。
注意:输入是一行一行给的,而统计是按一列一列来的,所以一定要先把整块花生地存起来再统计。
参考代码
// 运气最好的人:编号j的人负责摘第j列,求每列之和,输出和最大的人的编号和花生数 #include <iostream> using namespace std; int a[105][105]; int main() { int m, n; cin >> m >> n; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> a[i][j]; // 逐行读入花生地 int who = 1, mx = -1; // who保存最佳编号,mx保存最大值 for (int j = 0; j < n; j++) { // 枚举每一列(每个人负责的列) int s = 0; for (int i = 0; i < m; i++) s += a[i][j]; // 这一列的花生总数 if (s > mx) { mx = s; who = j + 1; } // 找到更大值就更新 } cout << who << " " << mx << endl; return 0; }复杂度分析
一共有 m×n 棵花生,读入和统计各遍历一遍,时间复杂度 O(m×n)。用一个 m×n 的二维数组存花生地,空间复杂度 O(m×n)。
- 1