木头切割

[MrLeihe]

简介

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

ps: 截断的长度必须是整数

输入两行，第一行n, k，第二行为数组序列。输出最大值。

输入
5 5
4 7 2 10 5
输出
4
解释：如图，最多可以把它分成5段长度为4的木头

ps:数据保证有解，即结果至少是1。

代码实现

方法一：暴力法

var clubSlice = function (k, nums) {
  var max = Math.max(...nums)
  var m = 1
  var res = 0
  while (m <= max) {
    var count = 0
    for (let i = 0; i < nums.length; i++) {
      // 计算在每个木棍中可切断次数
      count += Math.floor(nums[i] / m)
    }
    // 比较与 k 的大小，小于 k，则退出循环
    if (count >= k) {
      res = m
      m++
      count = 0
    } else {
      break
    }
  }
  return res
}

方法二：二分

var clubSlice = function (k, nums) {
  var m = 1
  // 先排序
  nums.sort((a, b) => a - b)
  var left = 0
  var right = nums[nums.length - 1]
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2)
    console.log('mid:', mid)
    var count = getCount(nums, mid)
    if (count >= k) {
      m = mid
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return m
}

var getCount = function (nums, mid) {
  var count = 0
  for (let i = 0; i < nums.length; i++) {
    count += Math.floor(nums[i] / mid)
  }
  return count
}