题解 | 小红的矩阵染色

#include <algorithm>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;            // n行, m列, 可操作次数k
    vector<vector<char>> a(n + 1, vector<char>(m + 1, '0'));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }

    vector<pair<int, int>> ans;    // 记录每列中连续'o'段的信息：<连续长度, 是否至少有一个'o'>
    for (int j = 1; j <= m; ++j) {
        int tem = 0;               // 当前连续'o'的个数
        int f = 0;                 // 该段是否含有'o'
        for (int i = 1; i <= n; ++i) {
            if (a[i][j] == 'o') f = 1;
            if (a[i][j] == 'o' && a[i-1][j] == 'o') {
                tem++;             // 遇到连续两个'o'时计数增加
            }
            // 当遇到不是'o' 或 到达最后一行时，结束当前段
            if (a[i][j] != 'o' || i == n) {
                ans.emplace_back(tem, f);
                f = 0;
                tem = 0;
            }
        }
    }

    // 按连续长度降序排序
    sort(ans.begin(), ans.end(), greater<>());

    int res = 0;
    for (auto [t, f] : ans) {
        if (t != 0) {
            int take = min(k, t + f);   // 可以操作的最大次数（与k和段长相关）
            res += take - 1;            // 每次操作增加的结果
            k -= take;                  // 剩余操作次数
        }
        if (k <= 0) break;
    }
    cout << res << endl;
    return 0;
}