题解 | 小红的矩阵染色

每日一题:

第一次看还以为是相邻的就得分 这样一想就打了个寒颤,仔细看才发现只用看垂直

一开始放一个r没有得分,后面每在这个r后面接一个r都得一分,所以尽量找足够长的,这样就不用另起炉灶.

排个序贪心一下

void solution::solve()
{
    int n,m,k;cin>>n>>m>>k;
    vector<string>g(n);
    for(int i=0;i<n;i++)cin>>g[i];
    vector<int>res;
    for(int j=0;j<m;j++)
    {
        int cnt = 0;
        for(int i=1;i<n;i++)
            if(g[i][j]==g[i-1][j]&&g[i][j]=='o')
                cnt++;
            else
            {
                if(cnt)
                    res.push_back(cnt);
                cnt=0;
            }
        if(cnt)res.push_back(cnt);
    }
    // 获得cnt需要cnt+1的格子
    sort(res.rbegin(),res.rend());
    int ans = 0;
    for(auto u:res)
    {
        // cout<<u<<endl;
        if(!k)break;
        ans += min(k-1,u);
        k -= min(k,u+1);
    }
    cout<<ans<<endl;
}