BISHI45　小红的矩阵染色¶

简单通过率 32.06%python3样例通过牛客 AC贪心

讲解章节：贪心

一句话

至多染红 k 个空格，每对「上下相邻的红格」得 1 分。

解题思路¶

这题考什么¶

得分 = 红格中「正下方也是红」的格子数 = 竖直相邻红格对数。黑格 '*' 把每一列切成若干段连续的 'o'，不同段之间永远不可能相邻，所以问题分解成：给定若干段，段长为 L_1, L_2, ...，在一段里染 c 个格子（显然要染连续的一段才划算）得分 c - 1（c >= 1）。

于是总得分 = (用掉的格子数) - (用到的段数)。预算 k 固定的前提下，要让得分最大，就要「用满预算」并且「用到的段数最少」—— 把段按长度从大到小排序，依次填满即可（长度 1 的段永远白给 0 分，并且会额外占用 1 个格子，直接跳过）。

验算样例 1（4x4, k=3）：各列的 'o' 连续段长度是 1,1 / 2,1 / 1,1 / 2,1，最大的段长 2，花 2 个格子得 1 分，剩 1 个预算不够再开一段（开新段要先垫 1 个格子才有分），答案 1 ✓。样例 2：中间那列是长度 3 的整段，k=3 全用上得 2 分 ✓。

数据规模与复杂度¶

n,m <= 1e3，共 1e6 个格子，必须 O(nm) 且常数要小。做法：把 n 行按列转置成 m 个 bytes，再用 bytes.split(b'') 在 C 层一次性切出所有段，避免 Python 层的百万次循环。排序段长 O(段数 log 段数)，段数 <= n*m。

坑在哪¶

分数按「格子」算而不是按「对」重复计：一段染 c 个连续格子只有 c-1 分，不是 c 分；开一段的第一个格子是纯成本；
剩余预算 < 2 时再开新段没有任何收益，要及时 break；
段长为 1 的段一律无用，排序后遇到就可以停；
输入含 n 行字符串，用 buffer.read().split() 按空白切正好把每行切出来（行内没有空格），第一行三个数字在前；
得分只看「正下方」，同一行左右相邻的红格不得分，所以按列拆解是对的，按行或按连通块拆都会算错。

贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI45.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1]); k = int(data[2])
    rows = data[3:3 + n]

    # 第一步：把矩阵按列切成一根根「连续空白段」，得到一张段长表
    lens = []
    for col in zip(*rows):                      # 转置：每个 col 是该列的字节元组
        for seg in bytes(col).split(b"*"):      # 黑格把列切成若干连续空白段
            if len(seg) >= 2:                   # 长度 1 的段最多得 0 分，直接不入表
                lens.append(len(seg))
    lens.sort(reverse=True)                     # 优先填最长的段，段数用得最少

    # 第二步：按段长从大到小分配预算，每段贡献「染的格子数 - 1」
    ans = 0
    rest = k                                    # 剩余可染格子数
    for L in lens:
        if rest < 2:                            # 不足 2 个格子凑不出一对，后面全无收益
            break
        c = L if L <= rest else rest            # 段能填满就填满，否则用光剩余预算
        ans += c - 1                            # 一段里染 c 个连续格子得 c-1 分
        rest -= c
    print(ans)


main()

BISHI45 小红的矩阵染色¶