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

题目链接

小红的矩阵染色

题目描述

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

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

解题思路

这是一个典型的资源分配优化问题，可以用贪心策略解决。我们的目标是用有限的资源（最多染 $k$ 个格子）来获得最大的分数。

1. 分析得分方式

分数是由垂直相邻的一对红色格子产生的。具体来说，一对上下的红色格子可以为上面的那个格子贡献1分。
在一个长度为 $L$ 的垂直连续白色块中，如果我们染了其中的 $c$ 个格子（ $c \le L$ ），我们最多能得到 $c-1$ 分（当这 $c$ 个格子是连续的时）。

2. 确定贪心策略 问题的本质是：我们有 $k$ 个染色机会（资源），以及多个“项目”（即矩阵中每一列的连续白色块）。我们应该如何分配资源给这些项目，以获得最大总收益（分数）？

项目与收益：
- 一个“项目”就是一个长度为 $L$ 的连续垂直白色块。
- 向这个项目投入 $c$ 个资源（染 $c$ 个格子，其中 $2 \le c \le L$ ），能获得的最大收益是 $c-1$ 分。
- 投入 $0$ 或 $1$ 个资源，收益为 $0$ 。
边际效益分析：
- 对于任何一个项目，投入第2个资源时，收益从0变为1，边际效益是1。
- 投入第3个资源时，收益从1变为2，边际效益也是1。
- ......
- 只要项目容量未满，每多投入1个资源，就能稳定地多获得1分。唯一的“额外成本”在于启动项目：第一个格子不产生分数，我们必须投入至少第二个格子才能开始得分。
贪心选择：
- 为了最大化总分（ $\sum(\text{投入} - 1)$ ），我们应该最大化总投入，同时最小化“启动成本”的总和。
- “启动成本”的总和就等于我们启动的“项目”数量。
- 因此，策略应该是将资源 $k$ 优先集中投入到最大的项目中，因为这样可以减少启动的项目数量，从而减少分数上的损失（每个项目都有一个不产生分数的格子）。

3. 算法步骤

识别项目：遍历矩阵的每一列，找出所有长度大于等于2的连续白色块，记录它们的长度。
排序：将所有找到的块长度按降序排序。
分配资源：遍历排好序的块。对于每个块，尽可能多地投入资源（即将它填满），直到预算 $k$ 耗尽。
计算总分：累加每个被投入资源的块所产生的分数。对于一个投入了 $c$ 个格子的块，它贡献的分数是 $c-1$ 。

代码

c++
java
python

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

using namespace std;

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

    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.begin(), block_lengths.end(), greater<int>());

    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);
    }
}

import sys

def solve():
    n, m, k = map(int, sys.stdin.readline().split())
    matrix = [sys.stdin.readline().strip() 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)$ 。