题解 | 小红的矩阵染色

#include <iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<functional>
int main() {
   int n,m,k;
   cin>>n>>m>>k;
   vector<vector<char>>v(n,vector<char>(m));
   vector<int>v_L;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            v[i][j]=c;
        }
    } 
   //按照列来遍历 找出所有大于等于2的格子
   for(int j=0;j<m;j++){
       int L=0;
    for(int i=0;i<n;i++){
         if(v[i][j]=='o'){
             L++;
         }
         if(v[i][j]=='*'||i==n-1){
            if(L>=2){
             v_L.push_back(L);
             }
             L=0;
         }
    }
   }//贪心
   //因为开始需要先涂两个格子才能开始加1分 所以将最长的格子放在前面 确保往下涂一格的加1分最多
   sort(v_L.begin(),v_L.end(),greater<int>());  
    int score=0;
   for(int i=0;i<v_L.size();i++){
      if(k==0||k==1){//当前已经不支持涂两个格子得一分
        break;
      }
      if(k>=2){//支持涂两个格子得一分
       v_L[i]-=2;
       k-=2;
       score++;
       }
      while(v_L[i]!=0){//往下继续涂一格得一分
       if(k==0){
            break;
        }
        v_L[i]-=1;
        k-=1;
        score++;
      }
   }
   cout<<score;
      



}
// 64 位输出请用 printf("%lld")