题解 | 小红的矩阵染色

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{
	int n,m,k,ans=0;
	cin >> n >> m >> k;
	string s[n];
	priority_queue<int>pq;
	for(int i=0;i<n;i++) cin >> s[i];
	for(int j=0;j<m;j++)//双指针处理 找出每个连续段的长度存储到优先队列中
	{
		int l=0,r=0;
		for(l=0,r=0;l<n&&r<n;)
		{
			if(s[r][j]=='*'&&s[l][j]=='o')
			{
				pq.emplace(r-l);
				r=l=r+1;
			}
			else if(s[r][j]=='*'&&s[l][j]=='*')
			{
				r=l=r+1;
			}
			else if(r==n-1&&s[r][j]=='o'&&s[l][j]=='o')
			{
				pq.emplace(r-l+1);
				break;
			}
			else r++;
		}
	}
	//cout << pq.top() << "\n";
	while(!pq.empty()&&k>1)//取出最大值处理 直到k小于2（当k=1时去涂色也无效）
	{
		int temp=pq.top();
		//cout << temp << " ";
		if(temp!=1&&k>=temp)
		{
			k-=temp;
			ans+=temp-1;
		}
		else if(temp!=1&&k<temp)//注意当k大于1时 碰到比k大的连续段 直接全部涂上去就行 ans加k-1
		{
			ans+=k-1;
			k=0;
		}
		pq.pop();
	}
	cout << ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}