[语言月赛 202312] 颜料覆盖 题解

· · 题解

Source & Knowledge

2023 年 12 月语言月赛，由洛谷网校入门计划/基础计划提供。

题目大意

给定一个 n 行 m 列的矩阵 a。求每一行中的最大值和这个最大值之前有多少个非 0 值比它小。

题目分析

本题考察对二维循环结构的运用。

对于「这个最大值之前有多少个非 0 值比它小」，略微琢磨便可发现，在最大值唯一的情况下，「比最大值小」是一定成立的。因此，题目的第二个任务可以转化为「求这个最大值之前有多少个非 0 值」。

对于第一个任务，可以使用「擂台法」轻松解决。擂台记录当前最大值和最大值的位置。读入元素时和最大值比较，如果更大则更新擂台。

for (int i = 1; i <= n; ++i) {
    int max_val = -1, max_pos = -1;
    for (int j = 1; j <= m; ++j) {
        int x;
        cin >> x;
        if (x > max_val) {
            max_val = x;
            max_pos = j;
        }
    }
}

对于第二个任务，可以考虑到，我们在读入元素的同时计数非 0 元素个数即可。在擂台中额外记录此时的非 0 元素个数，在「擂台法」的同时更新即可。

for (int i = 1; i <= n; ++i) {
    int max_val = -1, max_pos = -1, max_cnt = -1;
    int cnt = 0; 
    for (int j = 1; j <= m; ++j) {
        int x;
        cin >> x;
        if (x != 0) ++cnt;
        if (x > max_val) {
            max_val = x;
            max_pos = j;
            max_cnt = cnt; 
        }
    }
}

最后输出时，需要注意最大值自身是否有被统计到「个数」中。

视频讲解