题解 | 小红的矩阵染色

本题使用贪心与排序算法。由题意可知，每次最开始染色时需要染色两个空白格子得1分，但若上一个格子已被染成红色，则只需再染一个格子便可得1分，故最开始需要找到当前连续空白长度最长的串，开始染色。记录所有列连续空白的长度并进行降序排序，每次处理这一连续空白串，而非单独的一个空格字符。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n,m,k,l,sum=0,s;
    cin>>n>>m>>k;
    vector<string> v(n);
    vector<int> v1;
    for(int i=0;i<n;i++) cin>>v[i];
    for(int j=0;j<m;j++){
        l=0;
        for(int i=0;i<n;i++){
            if(v[i][j]=='o') l++;
            else{
                if(l>=2) v1.push_back(l);        //记录连续空白串长度
                l=0;
            }
        }
        if(l>=2) v1.push_back(l);               //处理列末尾的空白串
    }
    sort(v1.rbegin(),v1.rend());
    for(auto i:v1){                            //以一个空白串为单位进行处理，而非一个可选染色的空白小格
        if(k==0) break;
        s=min(k,i);
        if(s>=2) sum+=(s-1);
        k-=s;
    }
    cout<<sum;
    return 0;
}