题解 | #[USACO 2010 Feb S]Chocolate Eating#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)


//https://ac.nowcoder.com/acm/problem/24724
func NC24724(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
    var N,D int
    Fscan(in, &N, &D)
    H := make([]int, N)
    for i := 0; i < N; i++ {
        Fscan(in, &H[i])
    }
    //============================
    var act []int
    l,r := 0, int(^(uint(0)) >> 1)
    for l <= r {
        x := l + (r - l) / 2
        if arr, ok := judge(x, H, D); ok {
            act = arr
            l = x + 1
        }else {
            r = x - 1
        }
    }
    //============================
    Fprintln(out, r)
    for i := 0; i < N; i++{
        if act[i] > 0 {
            Fprintln(out, act[i])
        }else {
            Fprintln(out, D)
        }
        
    }
}


func judge(x int, H []int, D int) ([]int, bool){
    act := make([]int, len(H)) // the day on which Bessie eats chocolate i
    ci, ch := 0, 0  
    for d := 1; d <= D; d++ {
        for ci < len(H) && ch < x {
            ch += H[ci]
            act[ci] = d 
            ci ++
        }
        // 这天凑不齐 x
        if ch < x {
            return act, false
        }
        ch /= 2
    }
    return act, true
}

func main() {
    NC24724(os.Stdin, os.Stdout)
}