题解 | 小红的矩阵染色

package main

import (
	"fmt"
	"sort"
)

// 优先填最大的列中连续子段
func main() {
    var n,m,k int
    fmt.Scanf("%d %d %d", &n,&m,&k)
    a := make([]string, n)
    for i:=0;i<n;i++{
        fmt.Scanf("%s", &a[i])
    }
    var b []int // 记录所有可能的得分段
    var top, bottom int 
    for j:=0;j<m;j++{
        top, bottom = 0, 0
        for i:=0;i<n;i++{
            if a[i][j] == 'o'{
                bottom++
                if i == n-1{ // 到最后一行
                    b = append(b, bottom - top)
                }
            }else {
                if bottom > top{
                    b = append(b, bottom - top)
                }
                top, bottom = i+1,i+1
            }
        }
    }

    // 降序排序
    sort.Slice(b, func(i, j int) bool{
        return b[i] > b[j]
    })
    
    var result,index int
    for index < len(b) && k>0{
        if b[index] <= k{
            k -= b[index]
            result += b[index] -1
        }else {
            result += (k-1)
            k = 0
        }
        index++
    }
    fmt.Println(result)
}