木材加工（洛谷）

2024-01-24 08:20

文章标签 加工洛谷木材

本文主要是介绍木材加工（洛谷），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

木材加工

题目背景

要保护环境

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

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

样例 #1

样例输入 #1

样例输出 #1

提示

数据规模与约定

对于 $100\%$ 的数据，有 $1\le n\le 10^5$ ， $1\le k\le 10^8$ ， $1\le L_i\le 10^8(i\in[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; // 初始切割得到小段的数量为0for(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和需要的小段数量kcin>>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;
}