木材加工题解（博客搬家）

题面

题目描述

木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有剩余），需要得到的小段的数目是给定的。当然，我们希望得到的小段木头越长越好，你的任务是计算能够得到的小段木头的最大长度。木头长度的单位是cm。原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。 例如有两根原木长度分别为11和21，要求切割成到等长的6段，很明显能切割出来的小段木头长度最长为5.

输入

第一行是两个正整数N和K(1 ≤ N ≤ 100000，1 ≤ K ≤ 100000000)，N是原木的数目，K是需要得到的小段的数目。 接下来的N行，每行有一个1到100000000之间的正整数，表示一根原木的长度。

输出

能够切割得到的小段的最大长度。如果连1cm长的小段都切不出来，输出”0”。

样例输入

3 7 232 124 456

样例输出

114

分析题目

看起来有点复杂，其实很简单。 时间复杂度为 $O（log2n）$ 只要把木材每段长度二分就行了。 但这里判断方式不一样，我们为了要确保段数要符合条件，我们还需要一个判断。 判断方式就是累加段数，看看有没有小于段数，如果小就将左指针向右移至当前中点。 如果大于等于段数，就将右指针向左移至当前中点。

code

#include <bits/stdc++.h> using namespace std; long long a[100001],t=0,k,m,n; int js(int x) { register int i; t=0; for(i=1;i<=n;i++) { t+=a[i]/x; if(t>=k) return 1; } return 0; } int main() { long long s,l=0,r=0x7fffffff; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); while(l+1<r) { m=l+(r-l)/2; if(js(m)==1) l=m; else r=m; } printf("%d",l); return 0; }