题解 | 小红的矩阵染色

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        long k = sc.nextLong();
 
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++) {
            matrix[i] = sc.next().toCharArray();
        }
        // 遍历所有连续的垂直空白格段，记录下长度
        List<Integer> chainLengths = new ArrayList<>();
        // 先遍历每一列，将i j交换循环次序
        for(int j = 0; j < m; j++){
            int consecutiveWhite = 0;
            for(int i = 0; i < n; i++){
                if(matrix[i][j] == 'o'){
                    consecutiveWhite++;
                }else{
                    if(consecutiveWhite > 0){
                        chainLengths.add(consecutiveWhite);
                    }
                    consecutiveWhite = 0;
                }
            }
            // 当一整列都是空白的情况
            if(consecutiveWhite > 0){
                chainLengths.add(consecutiveWhite);
            }
        }
        // 将所有的垂直空白长度按照降序排列
        Collections.sort(chainLengths, Collections.reverseOrder());
        // 最优的贪心策略非常直接：总是优先在当前可用的、最长的垂直空白链上进行染色。
        long score = 0;
        for(int len : chainLengths){
            // 每次记分，都对减去相应的k值
            if(k <= 0) break;
            long toColor = Math.min((long) len, k);
            k -= toColor;
            if(toColor > 1){
                score += toColor - 1;
            }
        }
        System.out.println(score);
    }
}