题解 | 小红的矩阵染色

/*
先处理table的输入，再计算每列的连续oo的长度用vector存储，然后根据每一段连续oo的长度降序排列每一段连续oo。二维的问题就变成一维的了，最后再根据题目要求计算即可
*/


#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    long long k;
    cin >> k;
    vector<vector<char>>table(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char tmp;
            cin >> tmp;
            table[i][j] = tmp;
        }
    }
    if (k == 1) {
        cout << '0' << '\n';
        return 0;
    }
    vector<string>list;
    for (int j = 0; j < m; j++) {
        string temp;
        for (int i = 0; i < n; i++) {
            temp += table[i][j];
        }
        list.push_back(temp);
        temp.clear();
    }
    vector<int>list_continue_o_len;
    for (string s : list) {
        int continue_o = 0;
        for (char c : s) {
            if (c == 'o') {
                continue_o++;
            }
            if (c != 'o') {
                list_continue_o_len.push_back(continue_o);
                continue_o = 0;
            }
        }
        if (continue_o != 0) {
            list_continue_o_len.push_back(continue_o);
        }
    }
    sort(list_continue_o_len.begin(), list_continue_o_len.end(), greater<int>());
    int count = 0;
    for (int co : list_continue_o_len) {
        if (k >= co) {
            count += co;
            count--;
            k -= co;
        } else if (k > 1 && k < co) {
            count += k;
            count--;
            k = 0;
        }
        if (k == 0) {
            cout << count << '\n';
            return 0;
        }
    }
    cout << count << '\n';
}
// 64 位输出请用 printf("%lld")