算法笔记之木棒切割问题

一时失言乱红尘 2022-02-24 21:12 129阅读 0赞

<<算法笔记>>p134页

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0_size_16_color_FFFFFF_t_70][]

**问题分析：**

**此题的核心在于在满足切割后木棒数目符合要求外，求木棒的长度最大取值，这里很容易错解成一个符合条件的长度，并不是最大长度。**

**那么思考一下，这里的木棒最大长度代表着什么意思呢？**

**可以理解成 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;
    	}
    	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;
    }

代码总结：  
emm某些部分写得比较外行，但是问题不大，核心问题是写清楚了的。  
这里我最想说的是，这个问题被转换为了一类问题：**第一个满足条件的元素问题**

有两个简单的例题大家可以拿去参考：  
[二分法经典例题][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0_size_16_color_FFFFFF_t_70]: /images/20220225/48985264c2014f87840e86eb76d7d743.png
[Link 1]: https://blog.csdn.net/qq_41877184/article/details/88876488