自动搬运

查看原文

来自洛谷，原作者为

	dendky 生如春梦，乘桴于海

搬运于2025-08-24 23:14:11，当前版本为作者最后更新于2025-04-24 20:24:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

看见题目求最长的最短，考虑二分答案。二分中的 $mid$ 即为最长木棍的最小值，只需用 $\left \lceil \frac{a_i}{mid} \right \rceil$ 挨个计算一遍，求出修改次数判断是否小于等于 $m$ 即可。最后输出左边界为答案。

注意：如果 $a_i \bmod mid = 0$ 那么修改次数要减一，因为在这种情况下最后一刀会砍空，就是没砍到。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, a[300005];
bool check(int x) {
    int sum=0;
    for (int i=1; i<=n; i++) {
        sum+=a[i]/x;
        if (a[i]%x==0) sum--;
    }
    return sum>m;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>a[i];
    int l=1, r=1e9;
    while (l<=r) {
        int mid=l+r>>1;
        if (check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<l;
	return 0;
}