题解 | 小红的矩阵染色

“当每个红色的格子其下方的格子也为红色是得1分” -> 在垂直方向上连续k个空白格子最多可以得到k-1分

统计所有垂直方向上连续的空白格子，考虑到优先涂最长的格子是最优的，将空白格子长度逆序排序后遍历即可

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        String[] strs  = new String[n];
        for(int i = 0;i < n;i ++){
            strs[i] = in.next();
        }
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i < m;i++){
            int count = 0;
            for(int j = 0;j < n;j++){
                if(strs[j].charAt(i) == 'o')count ++;
                //检索所有上下连续的格子
                else{
                    list.add(count);
                    count = 0;
                }
            }
            list.add(count);
        }
        list.sort(Comparator.reverseOrder());//从高到低排序
        int result = 0;
        for(int length : list){
            if(k > length){
                //当前可以染色所有的格子
                result += length - 1;
                k -= length;
            }
            else{
                //只能染部分格子，得分为当前染色数-1
                result += k - 1;
                break;
            }
        }
        System.out.print(result);
    }
}