leetcode-go/oj/bytedance-2019-spring/no4/rope.go

package main

import (
	"fmt"
)

const eps float64 = 0.0001

func main() {
	var N, M int
	fmt.Scan(&N, &M)
	L := make([]int, N)
	max := 0
	for i := range L {
		fmt.Scan(&L[i])
		if max < L[i] {
			max = L[i]
		}
	}
	beg, end := 0.0, float64(max)
	for eps < end-beg { // Loop for 100 (or so) times is also valid.
		mid := (beg + end) / 2.0
		if solve(L, M, mid) {
			beg = mid
		} else {
			end = mid
		}
	}
	fmt.Printf("%.2f", beg)
}

func solve(L []int, M int, l float64) bool {
	cnt := 0
	for i := range L {
		length := float64(L[i])
		cnt += int(length / l)
	}
	return M <= cnt
}