小红的矩阵染色时间限制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≤10001 ≤ 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的数据规模。总结核心逻辑连续白色段越长染色得分效率越高贪心优先选择最长段染色。关键操作按列提取连续白色段、降序排序、逐段染色计算分数。效率保障线性遍历矩阵排序开销极小高效处理题目约束的矩阵规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll x,y,z;cinxyz;vectorvectorcharg(x,vectorchar(y));for(ll i0;ix;i){string s;cins;for(ll j0;jy;j)g[i][j]s[j];}vectorllv;for(ll i0;iy;i){ll c0;for(ll j0;jx;j){if(g[j][i]o)c;elseif(c){v.push_back(c);c0;}}if(c)v.push_back(c);}sort(v.begin(),v.end(),greaterll());ll res0;for(ll i0;i(ll)v.size();i){if(z0)break;if(zv[i]){z-v[i];resv[i]-1;}else{resz-1;z0;}}coutresendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}