P2440.木材加工 讲解

原题如下

---

P2440 木材加工

题目背景

要保护环境

题目描述

木材厂有 $n$ 根原木，现在想把这些木头切割成 $k$ 段长度均为 $l$ 的小段木头（木头有可能有剩余）。

当然，我们希望得到的小段木头越长越好，请求出 $l$ 的最大值。

木头长度的单位是 $\text{cm}$，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 $11$ 和 $21$，要求切割成等长的 $6$ 段，很明显能切割出来的小段木头长度最长为 $5$。

输入格式

第一行是两个正整数 $n,k$，分别表示原木的数量，需要得到的小段的数量。

接下来 $n$ 行，每行一个正整数 $L_i$，表示一根原木的长度。

输出格式

仅一行，即 $l$ 的最大值。

如果连 $\text{1cm}$ 长的小段都切不出来，输出 0。

输入输出样例 #1

输入 #1

3 7
232
124
456

输出 #1

114

说明/提示

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 10^5$，$1\le k\le 10^8$，$1\le L_i\le 10^8(i\in[1,n])$。

---

题目分析

$$将n个木材平均分成m份，每份要一样，问每份最多多少$$

测试用例分析

$$当到了114， 232/114 = 2段，124/114 = 1段，456/114 = 4，2+1+4=7；满足条件 $$$$当到了115， 232/115 = 2段，124/115 = 1段，456/115 = 3段 2+1+3=6，不满足 $$

边界分析

如果是l<=r 会导致无限循环

如l=5, r=6 mid = 5，若此时需要向右（l=mid），则 l = mid 会导致 l 还是5，无法跳出循环

为了避免相邻 就需要l+1<r 此时如果r=6，l最多等于4 避免相邻导致死循环

思路分析

二分

0.定义

#include<bits/stdc++.h> 
using namespace std;
#define int long long
int s,n;
int a[9000000];
int l=0,r=1e8;//题目规定
signed main(){//前面define int long long
  cin>>n>>s;
   for(int i=0;i<n;i++ ){
   		cin>>a[i];
   }
   while(l+1<r){//循环在l和r相邻时终止 也可以确保最小值为1，讲解见上（边界分析）
      int mid=(l+r)/2;
      int sum=0;
  }


}

1.找最大值

for(int i=0;i<n;i++){
      sum+=a[i]/mid;//作用是计算当每个元素被分割为mid个时，所有元素总共能分割出的份数之和

}

2.判断k

if(sum<s)
{
  r=mid;
}
else
{
  l=mid;
}//l始终指向此时的最大值，而 r 指向最小的值。最终 l（最大值） 即为答案。

3.输出

cout<<l;

题解

#include<bits/stdc++.h> 
using namespace std;
#define int long long
int s,n;
int a[9000000];
int l=0,r=1e8;

signed main(){
   cin>>n>>s;
   for(int i=0;i<n;i++ ){
   		cin>>a[i];
   } 

   while(l+1<r){//循环在l和r相邻时终止 也可以确保最小值为1
      int mid=(l+r)/2;
      int sum=0;
      for(int i=0;i<n;i++){
         sum+=a[i]/mid;

      }
      if(sum<s){l l始终指向此时的最大值，而 r 指向最小的值。最终 l（最大值） 即为答案。
         r=mid;

      }
      else{
         l=mid;
      }
      // sum=0;
   }
   cout<<l;






   return 0; 
}

1行代码解决h_h

```cpp
long long s,n,sum=0,a[9000000],l=0,r=1e8,mid;signed main(){__builtin_scanf("%d %d",&n,&s);for(int i=0;i<n;i++) __builtin_scanf("%d",&a[i]);while(l+1<r){mid=(r+l)/2;for(int i=0;i<n;i++) sum+=a[i]/mid;if(sum<s) r=mid,sum=0;else l=mid,sum=0;}__builtin_printf("%d",l);}