小红的矩阵染色

[题目链接](https://www.nowcoder.com/practice/f8b771318bb04490b7389cc35e148166)

思路

问题分析

给定一个 的矩阵，其中 * 是黑色格子，o 是白色格子。我们最多可以将 个白色格子染成红色。计分规则：如果一个红色格子的正下方也是红色格子，则该红色格子得 1 分。求最大得分。

关键观察：按列分析

得分只与同一列中上下相邻的红色格子有关，不同列之间互不影响。因此可以独立地看每一列。

在某一列中，黑色格子将白色格子分割成若干连续白色段。例如列 o o * o o o 包含两段，长度分别为 2 和 3。

段内染色的收益

对于一个长度为 的连续白色段，如果我们在其中连续染 个格子（），可以获得 分。

  • 染 1 个格子：0 分（没有上下相邻的红色对）
  • 染 2 个格子：1 分
  • 染 个格子： 分

注意：在段内，最优策略一定是染连续的格子，因为间断会浪费名额却不增加得分。

贪心策略

将得分公式写成全局视角：

$$

因为每个被使用的段（至少染 1 个格子）会"浪费"1 个格子在第一个位置上（不产生分数），之后每多染 1 个格子就多得 1 分。

要最大化得分，等价于在总名额 固定的情况下，最小化使用的段数。策略很直观：

  1. 将所有连续白色段按长度从大到小排序。
  2. 优先填满最长的段（用完整个段的名额）。
  3. 对最后一个不能填满的段，用剩余名额部分填充。

这样每个段尽可能多地分摊"第一格浪费"的成本，总段数最少，得分最高。

样例演示

样例 1：矩阵如下，。

*o*o
oooo
****
oooo

按列提取白色段：第 0 列 [, o, , o] → 段 [1, 1]；第 1 列 [o, o, , o] → 段 [2, 1]；第 2 列 [, o, , o] → 段 [1, 1]；第 3 列 [o, o, , o] → 段 [2, 1]。

所有段排序后：。用 ：先取长度 2 的段（花 2 格，得 1 分），再取长度 2 的段但只剩 1 格（花 1 格，得 0 分）。总得分 = 。

样例 2：矩阵如下，。

*o*
*o*
*o*

第 1 列有一个长度为 3 的段。取整段：花 3 格，得 分。

代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);

    vector<string> grid(n);
    for(int i = 0; i < n; i++){
        char buf[1001];
        scanf("%s", buf);
        grid[i] = buf;
    }

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

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

    int used = 0, score = 0;
    for(int i = 0; i < (int)segs.size() && used < k; i++){
        int take = min(segs[i], k - used);
        if(take >= 2) score += take - 1;
        used += take;
    }

    printf("%d\n", score);
    return 0;
}

import java.util.*;

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

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

        segs.sort(Collections.reverseOrder());

        int used = 0, score = 0;
        for (int i = 0; i < segs.size() && used < k; i++) {
            int take = Math.min(segs.get(i), k - used);
            if (take >= 2) score += take - 1;
            used += take;
        }

        System.out.println(score);
    }
}

import sys
input = sys.stdin.readline

def main():
    n, m, k = map(int, input().split())
    grid = []
    for _ in range(n):
        grid.append(input().strip())

    segs = []
    for j in range(m):
        cnt = 0
        for i in range(n):
            if grid[i][j] == 'o':
                cnt += 1
            else:
                if cnt > 0:
                    segs.append(cnt)
                cnt = 0
        if cnt > 0:
            segs.append(cnt)

    segs.sort(reverse=True)

    used = 0
    score = 0
    for s in segs:
        if used >= k:
            break
        take = min(s, k - used)
        if take >= 2:
            score += take - 1
        used += take

    print(score)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, m, k] = lines[0].split(' ').map(Number);
    const grid = [];
    for (let i = 1; i <= n; i++) {
        grid.push(lines[i]);
    }

    const segs = [];
    for (let j = 0; j < m; j++) {
        let cnt = 0;
        for (let i = 0; i < n; i++) {
            if (grid[i][j] === 'o') {
                cnt++;
            } else {
                if (cnt > 0) segs.push(cnt);
                cnt = 0;
            }
        }
        if (cnt > 0) segs.push(cnt);
    }

    segs.sort((a, b) => b - a);

    let used = 0, score = 0;
    for (let i = 0; i < segs.length && used < k; i++) {
        const take = Math.min(segs[i], k - used);
        if (take >= 2) score += take - 1;
        used += take;
    }

    console.log(score);
});

复杂度分析

  • 时间复杂度：。遍历矩阵提取白色段 ，排序段列表最多 ，贪心扫描 。
  • 空间复杂度：。存储矩阵和段列表。