题解 | 小红的矩阵染色

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

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    // 我们需要得到矩阵（一维字符串数组），然后对其按列遍历找到空白格，确定纵向连续空白格的长度，
    // 如果大于等于2，就压入空白格长度数组，之后按照降序重新排列空白格长度数组依次取出元素值，
    // 元素值-1即得到该元素的得分，这一块要注意保证k>=0的逻辑
    vector<string> s(n);
    vector<int> final_len_list;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int j = 0; j < m; j++) { // 这里可不是行，而是列
        int current_white_len = 0;
        for (int i = 0; i < n; i++) {
            if (s[i][j] == 'o') {
                current_white_len++;
            } else {
                if (current_white_len >= 2) {
                    final_len_list.push_back(current_white_len);
                }
                current_white_len = 0;
            }
        }
        // 注意，假设一整列都是空白格，那么就不会进入else，就不会把空白格长度压入队列，
        // 所以要添加对列末尾的判断
        if (current_white_len >= 2) {
            final_len_list.push_back(current_white_len);
        }

    }
    sort(final_len_list.rbegin(),
         final_len_list.rend());//最优的在最前，最差的最后
    int summ = 0; // 累计得分总和，等于空白格的长度-1
    for (int& length : final_len_list) {
        if (k == 0) {
            break;
        } else if (k - length > 0) {
            summ += length - 1;
            k -= length;
        } else if (k >= 2) { // 最后不能只写else，因为k == 1也是无效的
            summ += k - 1;
            k = 0;
        }
    }
    cout << summ;

}