题解 | #小红的矩阵染色#

题目链接

题目描述

给定一个 $n \times m$ 的矩阵，其中部分格子是黑色的（*），部分是空白的（o）。小红最多可以选择 $k$ 个空白格子，将它们染成红色。计分规则：如果一个红色格子的正下方也是红色，则这对相邻的红色格子贡献1分。求小红能获得的最大分数。

解题思路

本题要求在有限的染色次数（ $k$ ）下，最大化垂直相邻红格子的数量。这是一个资源分配问题，正确的贪心策略是解决问题的关键。

核心思想：优先染色最长的连续空白链

分析得分与成本：
- 在一个连续的垂直空白链中，如果我们染上 $c$ 个格子，我们可以获得 $c-1$ 分（要求 $c \ge 1$ ）。
- 这意味着，我们投入的每一个染色机会（除了第一个），都能稳定地转化为1分。
- 为了让我们的 $k$ 次染色机会产生最大的价值，我们应该优先把它们投入到能形成最长染色链的地方，因为长链能让我们获得最多的“1投入1产出”的机会。
贪心策略：
- 因此，最优的贪心策略非常直接：总是优先在当前可用的、最长的垂直空白链上进行染色。

实现步骤：

识别所有垂直链：
- 遍历矩阵的每一列，找出所有连续的垂直空白格段，并记录下它们的长度。
按长度排序：
- 将收集到的所有链长按从大到小的顺序排序。
贪心计算：
- 遍历排序后的链长列表（从最长的链开始）。
- 对于每个长度为 $L$ 的链：
  - 我们最多能在这条链上染 $L$ 个格子，但我们只剩下 $k$ 次机会。所以，实际能染的格子数是 $c = \min(k, L)$ 。
  - 更新我们剩余的染色机会：k -= c。
  - 这 $c$ 个格子能给我们带来 $c-1$ 分。累加到总分 score 中。
  - 如果 $k$ 已经用完，就可以提前结束。
- 最终得到的 score 即为最大分数。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    long long k;
    cin >> n >> m >> k;

    vector<string> matrix(n);
    for (int i = 0; i < n; ++i) {
        cin >> matrix[i];
    }

    vector<int> chain_lengths;
    for (int j = 0; j < m; ++j) {
        int consecutive_white = 0;
        for (int i = 0; i < n; ++i) {
            if (matrix[i][j] == 'o') {
                consecutive_white++;
            } else {
                if (consecutive_white > 0) {
                    chain_lengths.push_back(consecutive_white);
                }
                consecutive_white = 0;
            }
        }
        if (consecutive_white > 0) {
            chain_lengths.push_back(consecutive_white);
        }
    }

    sort(chain_lengths.begin(), chain_lengths.end(), greater<int>());

    long long score = 0;
    for (int len : chain_lengths) {
        if (k <= 0) break;
        long long to_color = min((long long)len, k);
        k -= to_color;
        if (to_color > 1) {
            score += to_color - 1;
        }
    }

    cout << score << endl;

    return 0;
}

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextLong();

        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            matrix[i] = sc.next().toCharArray();
        }

        List<Integer> chainLengths = new ArrayList<>();
        for (int j = 0; j < m; j++) {
            int consecutiveWhite = 0;
            for (int i = 0; i < n; i++) {
                if (matrix[i][j] == 'o') {
                    consecutiveWhite++;
                } else {
                    if (consecutiveWhite > 0) {
                        chainLengths.add(consecutiveWhite);
                    }
                    consecutiveWhite = 0;
                }
            }
            if (consecutiveWhite > 0) {
                chainLengths.add(consecutiveWhite);
            }
        }

        Collections.sort(chainLengths, Collections.reverseOrder());

        long score = 0;
        for (int len : chainLengths) {
            if (k <= 0) break;
            long toColor = Math.min((long)len, k);
            k -= toColor;
            if (toColor > 1) {
                score += toColor - 1;
            }
        }

        System.out.println(score);
    }
}

n, m, k = map(int, input().split())
matrix = [input() for _ in range(n)]

chain_lengths = []
for j in range(m):
    consecutive_white = 0
    for i in range(n):
        if matrix[i][j] == 'o':
            consecutive_white += 1
        else:
            if consecutive_white > 0:
                chain_lengths.append(consecutive_white)
            consecutive_white = 0
    
    if consecutive_white > 0:
        chain_lengths.append(consecutive_white)

chain_lengths.sort(reverse=True)

score = 0
for length in chain_lengths:
    if k <= 0:
        break
    
    to_color = min(length, k)
    k -= to_color
    if to_color > 1:
        score += to_color - 1

print(score)

算法及复杂度

算法：贪心
时间复杂度：
- 遍历矩阵并识别所有垂直链： $\mathcal{O}(n \cdot m)$ 。
- 排序链长列表，其大小最多为 $n \cdot m$ ： $\mathcal{O}(n \cdot m \log(n \cdot m))$ 。
- 遍历排序后的链长列表进行计算： $\mathcal{O}(n \cdot m)$ 。
- 总体时间复杂度由排序主导，为 $\mathcal{O}(n \cdot m \log(n \cdot m))$ 。
空间复杂度：需要存储矩阵和链长列表，空间复杂度为 $\mathcal{O}(n \cdot m)$ 。