思路：贪心 大根堆 双指针

首先，我们需要理解题目的要求，即我们需要将不多于$k$个白色格子变成红色，以使得最多的红色格子纵向相邻。

解决这个问题的关键在于如何选择变色的白色格子。我们可以观察到，对于某一列连续出现的白色格子，记其数量为$cnt$，我们最多可以得到$cnt-1$个优美的格子

具体实现时，我们可以使用一个优先队列来存储每一列连续出现的白色格子的数量。优先队列的顶部是数量最多的格子。然后，我们每次从优先队列中取出一段格子进行变色，直到我们已经变色了$k$个格子。

通过这种方式，我们可以保证每次变色都能得到最多的优美的格子，从而得到最终的答案。

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
char g[N][N];
int n,m,k;
int main(){
    cin>>n>>m>>k;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>g[i][j];
        }
    }
    priority_queue<int>heap; //大根堆
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(g[j][i]!='o')continue;
            int k=j;
            while(k<n&&g[k][i]=='o')k++;
            int cnt=k-j;
            heap.push(cnt);
            j=k-1;
        }
    }
    int res=0;
    while(k&&heap.size()){
        int t=heap.top();heap.pop();
        res+=min(t,k)-1;
        k=max(0,k-t);
    }
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int[] h = new int[m];
        PriorityQueue<Integer> highs = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        scanner.nextLine();
        for (int i = 0; i < n; i++) {
            String s = scanner.nextLine();
            for (int j = 0; j < m; j++) {
                if(s.charAt(j)=='o'){
                    h[j]++;
                }else {
                    if(h[j]!=0){
                        highs.add(h[j]);
                        h[j]=0;
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if(h[i]!=0){
                highs.add(h[i]);
            }
        }
        int res=0;
        while (k>0&& !highs.isEmpty()){
            Integer high = highs.poll();
            if(k>=high){
                k=k-high;
            }else {
                res+=k-1;
                break;
            }
            res+=high-1;
        }
        System.out.println(res);
    }
}

Python

import heapq

n, m, k = map(int, input().split())
g = [list(input()) for _ in range(n)]

heap = []
for i in range(m):
    j = 0
    while j < n:
        if g[j][i] != 'o':
            j += 1
            continue
        cnt = 0
        while j < n and g[j][i] == 'o':
            cnt += 1
            j += 1
        heapq.heappush(heap, -cnt)

res = 0
while k and heap:
    t = -heapq.heappop(heap)
    res += min(t, k) - 1
    k = max(0, k - t)

print(res)

题目描述

小红得到了一个矩阵。

该矩阵有若干个格子是黑色的，其余为白色，小红希望将不多于 $k$ 个白色格子变成红色。特殊的，如果有两个红色格子纵向相邻，小红会把上面的红色格子看作是“优美的”。

小红想知道，最多可以有多少个优美的格子？

输入格式

第一行三个整数 $n,m,k$，分别表示矩阵的行数和列数以及最多可以改变颜色的格子数。

接下来输入一个 $n \times m$ 的矩阵，表示矩阵的初始形态，其中 * 表示该格子为黑色，o 表示白色。

$1 \le n,m \le 1000$

$1 \le k \le n \times m$

输出格式

一个整数表示答案。

4 4 3
*o*o
oooo
****
oooo

1