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

题目链接

小红的矩阵染色

题目描述

小红有一个 $n \times m$ 的矩阵，其中一些格子是黑色的 ('*')，另一些是白色的 ('o')。她最多可以把 $k$ 个白色格子染成红色。

计分规则是：如果一个红色格子下方相邻的格子也是红色，那么这个红色的格子可以获得1分。请问小红最多可以得到多少分？

解题思路

这是一个典型的贪心策略问题。我们的目标是用有限的资源（最多染 $k$ 个格子）来获得最大的收益（分数）。

1. 分析得分方式与成本

得分方式：分数只能由垂直相邻的一对红色格子产生。具体来说，一对上下的红色格子可以为上面的那个格子贡献1分。
成本分析：为了获得分数，我们必须至少染两个垂直相邻的白色格子。
- 染一对垂直相邻的格子（2个），获得1分。成本为2。
- 如果在这对格子的基础上，再染下方相邻的第3个格子，我们只需要多花1个格子的成本，就能额外再获得1分。边际成本为1。
- 同理，继续向下扩展红色区域，每多染1个格子，就能多得1分。

2. 确定贪心策略 从成本分析中可以看出，获得分数的成本有两种：

初始成本：从无到有地创造一个得分对，需要染2个格子，成本为2。
扩展成本：在已有的红色格链上向下扩展一格，只需要染1个格子，成本为1。

显然，扩展成本（1）低于初始成本（2）。因此，我们的贪心策略应该是优先花费成本为1的操作，再花费成本为2的操作。

3. 算法步骤

识别机会：遍历整个矩阵，找出所有可以染色的机会。具体来说，就是找到每一列中，所有连续的白色格子组成的垂直块。
计算成本：对于一个长度为 $L$ 的垂直块，它最多可以贡献 $L-1$ 分。
- 获得第1分，需要染2个格子（成本为2）。
- 获得后续的 $L-2$ 分，每一分都只需要多染1个格子（成本为1）。
收集所有成本：我们可以创建一个列表，记录下获得每一分所需要的最小成本。遍历所有找到的垂直块（长度为 $L \ge 2$ ），对于每个块，向成本列表中添加一个 2 和 $L-2$ 个 1。
贪心选择：将成本列表升序排序。然后从头开始遍历，依次“购买”分数，直到预算 $k$ 耗尽。
- 维护当前分数 score 和剩余预算 k。
- 对于列表中的每个成本 c，如果 k >= c，则 score 加1，k 减 c。
- 如果 k < c，则无法购买，结束循环。
最终结果：循环结束后得到的 score 就是最大分数。

代码

c++
java
python

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

using namespace std;

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

    vector<int> block_lengths;
    // 按列遍历，找出所有垂直的白色块
    for (int j = 0; j < m; ++j) {
        int current_block_length = 0;
        for (int i = 0; i < n; ++i) {
            if (matrix[i][j] == 'o') {
                current_block_length++;
            } else {
                if (current_block_length >= 2) {
                    block_lengths.push_back(current_block_length);
                }
                current_block_length = 0;
            }
        }
        // 处理列末尾的块
        if (current_block_length >= 2) {
            block_lengths.push_back(current_block_length);
        }
    }

    sort(block_lengths.rbegin(), block_lengths.rend());

    int score = 0;
    for (int length : block_lengths) {
        if (k == 0) break;
        int cells_to_dye = min(k, length);
        if (cells_to_dye >= 2) {
            score += cells_to_dye - 1;
        }
        k -= cells_to_dye;
    }

    cout << score << endl;

    return 0;
}

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            matrix[i] = sc.next().toCharArray();
        }

        List<Integer> blockLengths = new ArrayList<>();
        // 按列遍历，找出所有垂直的白色块
        for (int j = 0; j < m; j++) {
            int currentBlockLength = 0;
            for (int i = 0; i < n; i++) {
                if (matrix[i][j] == 'o') {
                    currentBlockLength++;
                } else {
                    if (currentBlockLength >= 2) {
                        blockLengths.add(currentBlockLength);
                    }
                    currentBlockLength = 0;
                }
            }
            // 处理列末尾的块
            if (currentBlockLength >= 2) {
                blockLengths.add(currentBlockLength);
            }
        }

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

        int score = 0;
        for (int length : blockLengths) {
            if (k == 0) break;
            int cellsToDye = Math.min(k, length);
            if (cellsToDye >= 2) {
                score += cellsToDye - 1;
            }
            k -= cellsToDye;
        }

        System.out.println(score);
    }
}

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

    block_lengths = []
    # 按列遍历，找出所有垂直的白色块
    for j in range(m):
        current_block_length = 0
        for i in range(n):
            if matrix[i][j] == 'o':
                current_block_length += 1
            else:
                if current_block_length >= 2:
                    block_lengths.append(current_block_length)
                current_block_length = 0
        
        # 处理列末尾的块
        if current_block_length >= 2:
            block_lengths.append(current_block_length)

    block_lengths.sort(reverse=True)

    score = 0
    for length in block_lengths:
        if k == 0:
            break
        cells_to_dye = min(k, length)
        if cells_to_dye >= 2:
            score += cells_to_dye - 1
        k -= cells_to_dye
            
    print(score)

solve()

算法及复杂度

算法：贪心
时间复杂度：主要开销在于遍历矩阵和排序块长度列表。遍历矩阵的时间是 $\mathcal{O}(n \cdot m)$ 。块的数量最多为 $\mathcal{O}(n \cdot m)$ ，对其排序的时间是 $\mathcal{O}(n \cdot m \cdot \log(n \cdot m))$ 。因此，总时间复杂度为 $\mathcal{O}(n \cdot m \cdot \log(n \cdot m))$ 。
空间复杂度：需要 $\mathcal{O}(n \cdot m)$ 的空间来存储矩阵和块长度列表。因此，总空间复杂度为 $\mathcal{O}(n \cdot m)$ 。