【刷题笔记】--二分-P2440 木材加工

题目： 

思路： 

先在所有树中找到最长的树，从 1 到 这个最长的树的长度 的所有数作为二分查找的值，让每棵树除这个值，表示可以切出几段出来，累加在一起得到s，s表示一共有几段。s与k比较，如果s==k，表示找到了切出每段的长度，但此时并不能就结束了，也有可能这个长度再长一点，也可以切出我们要的k段。

一开始写的错误代码：

#include<stdio.h>
int cmp(const void *a,const void *b){return *(int *)a-*(int *)b;
}
int main(){long long n,k;//n是指有n根原木，k是指切出k段 scanf("%lld %lld",&n,&k);int i;long long tree[1000005];for(i=0;i<n;i++){scanf("%lld",&tree[i]);}long long sum=0;for(i=0;i<n;i++){sum+=tree[i];}	if(sum/k==0){printf("0");return 0;} qsort(tree,n,sizeof(tree[0]),cmp);long long left=1;long long right=tree[n-1];long long s=0;while(left<=right){s=0;long int mid=(left+right)/2;for(i=0;i<n;i++){s+=tree[i]/mid;}if(s>k){left=mid+1;}else if(s<k){right=mid-1;}else{printf("%lld",mid);break;}}return 0;
}

错就错在了我把s==k的情况单独分出来，然后就break了。

正确的代码：

#include<stdio.h>
int max(int a,int b){if(a>b){return a;}else{return b;}
}
int main(){long long n,k;//n是指有n根原木，k是指切出k段 scanf("%lld %lld",&n,&k);int i;long long tree[1000005];long long max1=0;for(i=0;i<n;i++){scanf("%lld",&tree[i]);max1=max(tree[i],max1);}long long sum=0;for(i=0;i<n;i++){sum+=tree[i];}	if(sum/k==0){printf("0");return 0;} long long left=1;long long right=max1;long long s=0;long long ans;while(left<=right){s=0;long long mid=(left+right)/2;for(i=0;i<n;i++){s+=tree[i]/mid;}if(s>=k){left=mid+1;}else{right=mid-1;}}printf("%lld",left-1);return 0;
}

 我们来重点分析这一段：

        if(s>=k){left=mid+1;}else{right=mid-1;}

printf("%lld",left-1);

其实这种只写两种情况，很好理解，当找到s==k时，left会继续往右走，跨过当前我们找到的这个mid的值， 如果右边还存在可以满足我们要的s==k的情况，就会继续进入s>=k的条件下，然后left又会跨过我们要的mid的值，而如果右边范围不存在s==k，或者s>k也不成立，那么就只会一直进入right=mid-1；此时，left一直没动，right一直在往左移，直到right移到了left左边，循环结束，输出left-1，就是我们当时要的mid值。

有个问题需要注意的是，为什么这个s==k的情况要连在s>k一起写，而不是和s<k，因为当找到s==k的情况时，我们还要再找有没有就是可以切出更长段的k段，所以肯定是要往数值大的方向去找，所以执行的语句是left=mid+1；而不是right=mid-1；

其实也可以拆开写：

        if(s>k){left=mid+1;}else if(s<k){right=mid-1;}else{left=mid+1;}			printf("%lld",left-1);