首页 > 分享 > 木材加工（洛谷）

木材加工（洛谷）

花匠小妙招
2024-12-18 14:59

木材加工

题目背景

要保护环境

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

样例 #1

样例输入 #1

3 7 232 124 456 1234 样例输出 #1

114 1

提示

数据规模与约定

对于 100 % 100% 100% 的数据，有 1 ≤ n ≤ 1 0 5 1le nle 10^5 1≤n≤105， 1 ≤ k ≤ 1 0 8 1le kle 10^8 1≤k≤108， 1 ≤ L i ≤ 1 0 8 ( i ∈ [ 1 , n ] ) 1le L_ile 10^8(iin[1,n]) 1≤Li≤108(i∈[1,n])。

#include<bits/stdc++.h> // 包含STL库，它包含了常用的头文件 using namespace std; #define ll long long // 定义long long 类型的别名为ll，方便后续使用 ll a[100010]; // 定义一个全局数组a用来存放n根原木的长度 ll n,k; // n为原木数量，k为需要切割得到的小段数量 // 定义一个检查函数，用来检查能否从原木中切割出长度为mid的k段木头 bool check(ll mid) { ll i; ll ans=0; // 初始切割得到小段的数量为0 for(i=0;i<n;i++) // 遍历所有原木 { ll b=a[i]; // b为当前原木的长度 while(b>=0) // 当b大于0时尝试切割 { b-=mid; // 试图切下一段长度为mid的木头 if(b>=0) ans++; // 如果剩余长度仍然大于等于0，成功切下一段，并计数 if(ans==k) return true; // 如果已经达到需要的k段，则返回true } } return false; // 如果尝试了所有可能仍未达到k段，则返回false } int main() { // 输入原木数量n和需要的小段数量k cin>>n>>k; ll i,j,max=0; for(i=0;i<n;i++) // 遍历n根原木 { cin>>a[i]; // 输入每根原木的长度 if(max<a[i]) max=a[i]; // 记录下所有原木中最长的一根 } int l=0,r=max; // 设置二分查找的初始左右边界 //二分查找——右边界 while(l<r) // 当左边界小于右边界时执行循环 { ll mid=(r+l+1)>>1; // 计算中间值，注意这里加1是为了避免死循环 if(check(mid)) l=mid; // 如果能够切出k段长度为mid的木头，则更新左边界 else r=mid-1; // 否则减小右边界 } cout<<r<<endl; // 输出结果，此时r即为最大可能的段长度 return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445