题解 | #[USACO 2010 Feb S]Chocolate Eating#
[USACO 2010 Feb S]Chocolate Eating
https://ac.nowcoder.com/acm/problem/24724
技巧
二分
思路
尝试快乐值 x ， 看是否每天都能达到。 二分找到满足条件的最大的值
实现
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)
}
