企业官网建设流程全解析

P16227 [蓝桥杯 2026 省 A] 切割木材

Link: https://www.luogu.com.cn/problem/P16227

题目描述

角落里，一台老旧的自动分装机正发出沉闷的轰鸣声。

小蓝站在流水线旁，准备将一批木材送入分装机。机器的挡板间距L LL是唯一可调参数，任何长度超过L LL的木段都会导致传送带卡死。显然，挡板间距越小，单位时间内的输送密度就越高。因此，小蓝希望将这个挡板间距L LL设定得尽可能小。

眼前有N NN根原始木材，第i ii根的长度为A i A_iAi​。小蓝可以对这些木材进行切割以满足长度要求，但由于锯片磨损，他全程最多只能进行K KK次切割。具体的切割规则如下：

1. 每次切割可以将一根木材切割为两段。
2. 分割后，新产生的两段木材的长度必须为正整数，且长度之和等于原木材的长度。

现在，请你为小蓝找出这个最小可行的挡板间距L LL，使得在总切割次数不超过K KK的前提下，切割后所有木段的最大长度不超过L LL。

输入格式

第一行包含两个整数N NN和K KK，分别表示原始木材的数量和最大切割次数。

第二行包含N NN个整数A 1 , A 2 , … , A N A_1, A_2, \ldots, A_NA1​,A2​,…,AN​，表示每根原始木材的长度。

输出格式

输出一个整数，表示最小可行的挡板间距L LL。

输入输出样例 #1

输入 #1

1 1 5

输出 #1

3

输入输出样例 #2

输入 #2

2 3 9 6

输出 #2

3

说明/提示

【评测用例规模与约定】

对于10 % 10\%10%的评测用例，1 ≤ N ≤ 100 1 \le N \le 1001≤N≤100，0 ≤ K ≤ 3 0 \le K \le 30≤K≤3，1 ≤ A i ≤ 10 3 1 \le A_i \le 10^31≤Ai​≤103。

对于50 % 50\%50%的评测用例，1 ≤ N ≤ 10 3 1 \le N \le 10^31≤N≤103，0 ≤ K ≤ 10 5 0 \le K \le 10^50≤K≤105，1 ≤ A i ≤ 10 5 1 \le A_i \le 10^51≤Ai​≤105。

对于100 % 100\%100%的评测用例，1 ≤ N ≤ 10 6 1 \le N \le 10^61≤N≤106，0 ≤ K ≤ 10 9 0 \le K \le 10^90≤K≤109，1 ≤ A i ≤ 10 9 1 \le A_i \le 10^91≤Ai​≤109。

Solution

1. 题意

若干段长度不尽相同的木材，长度为A 1 , A 2 , ⋯ , A n A_1,A_2,\cdots,A_nA1​,A2​,⋯,An​，限定不超过K KK次切割，最小化每段的最大长度L LL。

2. 分析

非常基础的二分问题。

不难看出如果某个间距L LL是可行的（即所需切割次数≤ K \le K≤K），那么所有大于L LL的间距也一定可行（因为允许的最大长度变大了，需要的切割次数只会更少或不变）。

如果L LL不可行，那么所有小于L LL的间距也一定不可行。

如此一来直接对L LL进行二分查找即可。

具体说来，长度为A i A_iAi​的木材，若要保证每一段长度不超过L LL，需要切割的次数是⌈ A i L ⌉ − 1 \left \lceil \dfrac{A_i}{L} \right \rceil - 1⌈LAi​​⌉−1。只需要让

∑ i = 1 N ( ⌈ A i L ⌉ − 1 ) ≤ K ⇒ ∑ i = 1 N ⌈ A i L ⌉ ≤ K + N \sum_{i=1}^N \left( \left \lceil \dfrac{A_i}{L} \right \rceil - 1\right) \le K \quad \Rightarrow \quad \boxed{\sum_{i=1}^N \left \lceil \dfrac{A_i}{L} \right \rceil \le K + N}i=1∑N​(⌈LAi​​⌉−1)≤K⇒i=1∑N​⌈LAi​​⌉≤K+N​

这个不等式成立，这就是二分的判别条件。

3. 代码

::::success[C#]

usingSystem;usingSystem.Collections.Generic;classP16227{staticvoidMain(){varinput=Console.ReadLine()?.Split();if(input==null||input.Length<2)return;intn=int.Parse(input[0]);longk=long.Parse(input[1]);vara=newint[n];intmaxLen=0;varline=Console.ReadLine()?.Split();if(line==null||line.Length<n)return;for(inti=0;i<n;i++){a[i]=int.Parse(line[i]);if(a[i]>maxLen)maxLen=a[i];}longleft=1,right=maxLen;while(left<right){longmid=left+(right-left)/2;longcuts=0;foreach(varxina){cuts+=(x-1)/mid;if(cuts>k)break;}if(cuts<=k){right=mid;}else{left=mid+1;}}Console.WriteLine(left);}}

::::

::::success[C++14]

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){intn;ll k;if(!(cin>>n>>k))return0;vector<int>a(n);intmax_len=0;for(inti=0;i<n;++i){cin>>a[i];if(a[i]>max_len)max_len=a[i];}ll left=1,right=max_len;while(left<right){ll mid=left+(right-left)/2;ll cuts=0;for(intx:a){cuts+=(x-1)/mid;if(cuts>k)break;}if(cuts<=k){right=mid;}else{left=mid+1;}}cout<<left<<endl;return0;}

::::