切木头.md

问题描述

给定长度为n的数组，每个元素代表一个木头的长度，木头可以任意截断，从这堆木头中截出至少k个相同长度为m的木块。已知k，求max(m)。

输入两行，第一行n, k，第二行为数组序列。输出最大值。数据保证有解，即结果至少是1。

输入

5 5
4 7 2 10 5

输出

4

解释

如图，最多可以把它分成5段长度为4的木头

---

对结果二分：从一到木棍最长的长度进行二分遍历，每次遍历的长度作为 i，检查是否可以将所有木头截出来 k 个长度为 i 的木块

package main

import "fmt"

func main() {
	n, k := 5, 5
	arrays := []int{4, 7, 2, 10, 5}
	fmt.Println(wood(n, k, arrays))
}

func check(arrays []int, m int) int {
	res := 0
	for i := range arrays {
		res += arrays[i] / m
	}
	return res
}

func wood(n, k int, arrays []int) int {
	l, r := 1, 1
	for i := range arrays {
		if r < arrays[i] {
			r = arrays[i]
		}
	}
	r++
	for l < r {
		mid := (l + r + 1) >> 1
		if check(arrays, mid) >= k {
			l = mid
		} else {
			r = mid - 1
		}
	}
	return l
}