小红的矩阵染色
时间限制：1秒 空间限制：256M
知识点：贪心 排序
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红拿到了一个矩阵，初始有一些格子被染成了黑色。现在小红希望把最多k kk个未被染成黑色的格子染成红色，具体的计分方式是：如果一个红色格子下方相邻的格子也是红色，那么这个红色格子可以获得1 11分。
小红想知道，最多可以得到多少分？
输入描述：
第一行输入三个正整数n , m , k n,m,kn,m,k，代表矩阵的行数和列数、以及小红最多可以染色的格子数量。
接下来的n nn行，每行输入一个长度为m mm的字符串，用来表示矩阵的初始染色情况。′ ∗ ′ '*'′∗′字符代表黑色，′ o ′ 'o'′o′字符代表白色。
1 ≤ n , m ≤ 1000 1≤n,m≤10001≤n,m≤1000
1 ≤ k ≤ n ∗ m 1≤k≤n∗m1≤k≤n∗m
输出描述：
一个整数，代表小红可以获得的最大分数。
示例1
输入：
4 4 3 *o*o oooo **** oooo输出：
1说明：
将矩阵染色成如下样式即可（′ r ′ 'r'′r′代表红色）：
\*r\*o oroo \**** oooo示例2
输入：
3 3 3 *o* *o* *o*输出：
2解题思路
本题核心是贪心算法+连续段统计，利用得分规则的特性最大化分数。根据规则：一列中连续染成红色的 t 个格子，可获得 t-1 分，连续段越长，单位染色数的得分效率越高。因此采用贪心策略：优先染色最长的连续白色段。首先遍历矩阵的每一列，提取被黑色格子分隔的所有连续白色格子段，记录各段长度；将所有连续段按长度降序排序，依次优先染色最长段，累加对应分数，若剩余染色名额不足则染部分格子计算分数，直到用完 k 次染色机会。算法时间复杂度O ( n m ) O(nm)O(nm)，完美适配n , m ≤ 1000 n,m≤1000n,m≤1000的数据规模。
总结
核心逻辑：连续白色段越长，染色得分效率越高，贪心优先选择最长段染色。
关键操作：按列提取连续白色段、降序排序、逐段染色计算分数。
效率保障：线性遍历矩阵，排序开销极小，高效处理题目约束的矩阵规模。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidsolve(){ll x,y,z;cin>>x>>y>>z;vector<vector<char>>g(x,vector<char>(y));for(ll i=0;i<x;i++){string s;cin>>s;for(ll j=0;j<y;j++)g[i][j]=s[j];}vector<ll>v;for(ll i=0;i<y;i++){ll c=0;for(ll j=0;j<x;j++){if(g[j][i]=='o')c++;elseif(c){v.push_back(c);c=0;}}if(c)v.push_back(c);}sort(v.begin(),v.end(),greater<ll>());ll res=0;for(ll i=0;i<(ll)v.size();i++){if(z<=0)break;if(z>=v[i]){z-=v[i];res+=v[i]-1;}else{res+=z-1;z=0;}}cout<<res<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}
