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

可定

发布于 2020-04-20 15:10:57

1K0

发布于 2020-04-20 15:10:57

文章被收录于专栏：细嗅蔷薇细嗅蔷薇

给出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;
}