木材加工(洛谷)

发布时间:2024年01月24日

木材加工

题目背景

要保护环境

题目描述

木材厂有 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

样例输出 #1

114

提示

数据规模与约定

对于 100 % 100\% 100% 的数据,有 1 ≤ n ≤ 1 0 5 1\le n\le 10^5 1n105 1 ≤ k ≤ 1 0 8 1\le k\le 10^8 1k108 1 ≤ L i ≤ 1 0 8 ( i ∈ [ 1 , n ] ) 1\le L_i\le 10^8(i\in[1,n]) 1Li?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;
}
文章来源:https://blog.csdn.net/m0_73841621/article/details/135797866
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。