切割木头

[编程题]切割木头

热度指数：637 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组，数组中的元素表示每个木头的长度，木头可以在任意位置截断。从这些木头中取出至少 k 个长度都为 m 的木头。请问 m 最大是多少。

数据范围：数组长度满足 $1 \le n \le 10^4 \$ ，木头长度满足 $1 \le val \le 10^9 \$ , $1 \le k \le 2\times 10^4 \$

示例1

输入

[1,2,3,4,5],3

输出

示例2

输入

[1,2,3,4,5],5

输出

示例3

输入

[1,2,3,4,5],7

输出

算法知识视频讲解

C++

已注销

class Solution {
public:
    int cutWood(vector<int>& a, int k) {
        int right = 0;
        for(auto i  : a)
            right = max(right, i);
        return binary(a, k, 1, right + 1);
    }
private:
    int stickNum(vector<int>& a, int k)
    {
        int ret = 0;
        for(auto i : a)
            ret += i / k;
        return ret;
    }
    int binary(vector<int>& a, int k, int left, int right)
    {
        int mid = 0;
        while(left < right)
        {
            mid = left + (right - left) / 2;
            if(stickNum(a, mid) < k)
                right = mid;
            else
                left = mid + 1;
        }
        return left - 1;
    }
    
};

将求解满足段数的最大木棒长度，改成使小于段数最小木棒长度，转换成upper_bound的形式。然后再将索引位置减一即可。

发表于 2022-07-27 19:52:48 回复(0)

世界杯2009

垃圾牛客，什么垃圾题目，词不达意，读不懂

发表于 2022-04-27 23:25:15 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param a int整型一维数组
# @param k int整型
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/707d98cee255448c838c76918a702be0?tpId=196&tqId=40513&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：山山ks
    算法：
        本题考查的是我们以长度m切割每根木头，判断是否能切割出大于等于k根长度为m的木头
        1. 对于m的选取，我们采用二分法，在区间[1, max(a)]中寻找
        2. 若切割之后，长度为m的木头数量小于k，说明m选大了，right = mid - 1；否则，我们缩小区间为[mid, right]。
    复杂度：
        时间复杂度：O(nlogn + nlogx)，n为a的长度，x为max(a)
        空间复杂度：O(n)
    """

    def cutWood(self, a, k):
        # write code here
        a.sort()

        left, right = 1, a[-1]
        n, m = len(a), 0
        while left < right:
            mid = left + (right - left + 1) / 2

            count = 0
            for i in range(n - 1, -1, -1):
                if a[i] < mid:
                    break
                count += a[i] / mid

            if count >= k:
                left = mid
            else:
                right = mid - 1

        return left


if __name__ == "__main__":
    sol = Solution()

    # a, k = [1, 2, 3, 4, 5], 3

    # a, k = [1, 2, 3, 4, 5], 5

    a, k = [1, 2, 3, 4, 5], 7

    res = sol.cutWood(a, k)

    print res

发表于 2022-06-28 17:27:16 回复(0)

今天也要躺平

class Solution {
public:
    // 判断是否能够切割出k个m长度的木头
    bool canCut(vector<int>& a, int k, int m) {
        int cnt = 0;
        for (auto num: a) {
            cnt += num / m;
            if (cnt >= k) return true;
        }
        return false;
    }
    // 二分，先排序，然后判断中间值是否满足
    int cutWood(vector<int>& a, int k) {
        sort(a.begin(), a.end());
        int l = a[0], r = a[a.size() - 1];
        
        while (l <= r) {
            int mid = (l + r) / 2;
            // 如果能够切割出k个mid长度的木头，则在右半区间取木头大小
            if (canCut(a, k, mid)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
};

发表于 2023-09-15 22:02:27 回复(0)

Java

skwan

import java.util.*;

public class Solution {
    /**
     *  二分法
     */
    public int cutWood (ArrayList<Integer> a, int k) {
        Collections.sort(a, Comparator.reverseOrder());
        int left = a.get(a.size() - 1), right = a.get(0);
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (canCut(a, mid, k)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    private boolean canCut(ArrayList<Integer> a, int m, int k) {
        if (k == 0) return true;
        for (int i = 0; i < a.size() && a.get(i) >= m; i++) {
            int cur = a.get(i);
            if (cur >= m) {
                while (cur >= m) {
                    cur -= m;
                    k--;
                    if (k <= 0) return true;
                }
            } else {
                return false;
            }
        }
        return false;
    }
}

发表于 2022-08-01 15:54:45 回复(0)