木棒切割问题——基于二分的思想

发布于 2020-02-20  374 次阅读


给出N根木棒,长度已知,现在切割这些木棒至少得到K根长度相等的木棒,求长度相等的木棒最长是多长。

举个栗子:

有N=3个木棒,长度10、24、15,要切成K=7段长度相等的木棒,那么可以得到的最长长度是L=6。这时候,第一根可以提供10/6=1段,第二根可以提供24/6=4段,第一根可以提供15/6=2段,达到了7段的要求。

这里有一个最基本的结论:如果L越长,那么K越少。

这样便可以得到本题的算法:二分思想。就是根据当前长度L来说能得到的木棒数小k和大K的大小来进行二分。

由于本题可以写成求解最后满足“小k<大K”的长度L(想想这话什么意思,挖坑,待解决),因此转换为求解第一个满足“小k<大K”的长度L,然后减1即可。

这里的木棒最大长度代表着什么意思呢?

可以理解成 MaxL+1 一定导致木棒数目至少K-1。

MaxL-1可能会导致木棒数目至少K+1,也可能数目不变为K。

因此这个求MaxL的问题,可以解释成为求 K-1木棒数目所需L,再让L-1,就得到了我们索要的最大长度MaxL。如果有疑问请往下面看,这是一个类型的解题方式。

#include <stdio.h>
int N; //N个木棒
//最长的木棒
int Max(int arr[]){
    int max=0;
    for(int i=0;i<N;i++){
        if(arr[i]>max){
            max=arr[i];
        }
    }
    return max;
}
//计算切割后小木棒总数
int f(int arr[],int L){
    int sum=0; //切成sum个小木棒
    for(int i=0;i<N;i++){
        sum=sum+arr[i]/L;
        /*这里L是怎么得出来的呢?
        这里的L是solve函数的mid
        这里木棒中的最大长度是24,则mid为12
        则第一遍sum=0+10/12=0;第二遍sum=0+24/12=2;
        第三遍sum=2+15/12=3;则最后sum为3
        则f(arr,mid)<K,因此right=mid,从而right=12
        此时left=0,right=12显然不符合循环跳出要求

        进而继续执行第二遍操作,将mid设为6,则L=6
        则第一遍sum=0+10/6=1;第二遍sum=1+24/6=5;
        第三遍sum=5+15/6=7;则最后sum为7
        则f(arr,mid)>=k,left=mid+1,从而left=7
        此时left=7,right=12显然不符合循环跳出要求

        进而继续执行第三遍操作,将mid设为9,则L=9
        则第一遍sum=0+10/9=1;第二遍sum=1+24/9=3;
        第三遍sum=3+15/9=4;则最后sum为4
        则f(arr,mid)<K,right=mid,从而right=9
        此时left=7,right=9显然不符合循环跳出要求

        进而继续执行第四遍操作,将mid设为8,则L=8
        则第一遍sum=0+10/8=1;第二遍sum=1+24/8=4;
        第三遍sum=4+15/8=5;则最后sum为5
        则f(arr,mid)<K,right=mid,从而right=8
        此时left=7,right=8显然不符合循环跳出要求

        进而继续执行第五遍操作,将mid设为7,则L=7
        则第一遍sum=0+10/7=1;第二遍sum=1+24/7=4;
        第三遍sum=4+15/7=6;则最后sum为6
        则f(arr,mid)<K,right=mid,从而right=7
        此时left=7,right=7显然符合循环跳出要求

        因此返回right-1=7-1=6。
        (这里为什么要返回right-1?挖坑,待解决)
    }
    return sum;
}
//二分法
int solve(int K,int arr[]){
    int left=0,right=Max(arr),mid;
    while(left<right){
        mid=(left+right)/2;
        if(f(arr,mid)<K){ //小木棒个数K-1时
            right=mid;
        }else{
            left=mid+1;
        }
    }
    return right-1; //返回长度
}
int main(){
    scanf("%d",&N); //木棒数目
    int arr[N]; //每个木棒的长度
    for(int i=0;i<N;i++){
        scanf("%d",&arr[i]);//N个木棒的原始长度
    }
    int K; //K个长度相同的小木棒
    scanf("%d",&K);
    printf("%d",solve(K,arr));
    return 0;
}

参考

算法笔记之木棒切割问题

本文标题:《木棒切割问题——基于二分的思想》

本文链接:https://wnag.com.cn/887.html

特别声明:除特别标注,本站文章均为原创,本站文章原则上禁止转载,如确实要转载,请电联:wangyeuuu@qq.com,尊重他人劳动成果,谢过~


正因为有要好好实现的梦想,所以今天也要好好加油。