题解 | 小红的矩阵染色

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

using namespace std;

int main() {
    // 加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    vector<int> segments;
    // 1. 遍历每一列，提取所有连续的 'o' 段长度
    for (int j = 0; j < m; j++) {
        int length = 0;
        for (int i = 0; i < n; i++) {
            if (mp[i][j] == 'o') {
                length++;
            } else {
                if (length > 0) segments.push_back(length);
                length = 0;
            }
        }
        if (length > 0) segments.push_back(length);
    }

    // 2. 贪心：优先填满长度更长的段
    // 因为每个段的第一个格子是“启动成本”，不给分。段越长，分数的产出率越高。
    sort(segments.rbegin(), segments.rend());

    int total_score = 0;
    int remaining_k = k;

    for (int len : segments) {
        if (remaining_k <= 0) break;

        // 实际能在这个段染色的数量
        int fill = min(remaining_k, len);
        
        // 如果填入的格子数 > 1，得分就是 fill - 1
        if (fill > 1) {
            total_score += (fill - 1);
        }
        
        remaining_k -= fill;
    }

    cout << total_score << endl;

    return 0;
}