题解 | 小红的矩阵染色

//如果超时就多提交两遍，多来两遍就过了
const rl = require("readline").createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();
const readline = async (): Promise<string> => (await iter.next()).value;
(async function (): Promise<number> {
    const [N, M, K] = (await readline()).split(" ").map(Number);
    let _map: Array<Array<number>> = [];
    let res: number = 0;
    let _max: number = 0;
    for (let _ = 0; _ < N; _++) {
        _map.push(
            (await readline()).split("").map((flag, index) => {
                if (_ === 0 && flag === "o") return 0;
                if (_ === 0 || flag === "*") return -1;
                else {
                    const temp = _map[_map.length - 1][index] + 1;
                    _map[_map.length - 1][index] = 0;
                    _max = Math.max(_max, temp);
                    return temp;
                }
            })
        );
        if (_max >= K - 1) return K - 1;
    }
    // console.log(_map)
    const _find: Array<number> = [0];
    for (let i = N - 1; i >= 0; i--) {
        for (let j = 0; j < M; j++) {
            if (_map[i][j]>=1) _find.splice(bisectLeft(_find, _map[i][j]),0,_map[i][j]);
        }
    }
    // console.log(_find)
    let tem = K;
    for(let i=_find.length-1;i>=0&&tem>1;i--){
        res+=Math.min(_find[i], tem-1);
        tem-=_find[i]+1;
    }
    return res;
})()
    .then((res) => console.log(res))
    .catch((err) => console.log(err))
    .finally(() => rl.close());
function bisectLeft(arr:Array<number>, x:number):number {
    let lo = 0,
        hi = arr.length;
    while (lo < hi) {
        const mid = (lo + hi) >>> 1;
        if (arr[mid] < x) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}