问题分析

本题是一个典型的最优化问题，具体为在满足特定约束（能够切出至少 段）的前提下，寻找参数（切出的长度）的最大值。 核心数学关系为：对于选定的裁剪长度 ，第 根原木棍能提供的段数为 。我们需要找到最大的整数 ，使得：

关键约束

  1. 数据范围：
    • ，这意味着我们的算法必须在 或 级别， 会超时。
    • 。虽然 和 很大，但我们并不需要创建一个大小为 的数组。需要注意的是，尽管 是 Int 范围，但如果不加以剪枝，单纯的累加可能会溢出 32 位整数（尽管本题逻辑中，一旦计数达到 即可停止，故不大可能溢出，但使用 64 位整数存储计数器是工程上的防御性编程习惯）。
  2. 解的单调性：
    • 如果长度 可行（能切出 段），那么任何比 小的长度 () 必然也由行（至少能切出同样多的段数）。
    • 如果长度 不可行（切出段数 ），那么任何比 大的长度也必然不可行。
    • 这种单调性是使用二分查找算法的充分条件。
  3. 边界情况：
    • 如果所有木棍的总长度都不足以切出 段（即即使 也不满足），答案应为 0。
    • 除法运算中除数不能为 0，二分查找的下界处理需谨慎。

算法：二分答案

由于直接计算最大长度极其困难，而验证一个给定的长度是否可行非常容易（线性时间），且问题的解空间具有明确的单调性，因此二分答案是本题的最优解法。

算法逻辑 我们将问题的求解转化为对答案范围的搜索：

  1. 搜索空间：答案不仅是非负整数，且一定在区间 内。更保守的右边界可以直接设为 。
  2. 判定函数：构建一个函数 check(Length)。该函数遍历所有木棍，计算以 Length 为标准能切出的总段数。如果总段数 ，返回 True，否则返回 False。
  3. 二分策略：
    • 如果在当前长度 mid 下 check(mid) 为真，说明 mid 可行，且更大的解可能存在于右半区间（包含 mid）。
    • 如果 check(mid) 为假，说明 mid 太长了，解一定在左半区间（不包含 mid）。

这种方法避免了暴力的枚举，将寻找解的过程从线性扫描转化为对数级扫描。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll K;
    cin >> N >> K;
    vector<ll> v(N);

    ll L = 1;
    ll R = 0;
    for (int i = 0; i < N; i++) {
        cin >> v[i];
        R = max(R, v[i]);
    }

    auto check = [&](ll length) -> bool {
        ll cnt = 0;
        for (ll x : v) {
            cnt += x / length;
            if (cnt >= K)
                return true;
        }
        return false;
    };

    ll ans;
    while (L <= R) {
        ll mid = L + (R - L) / 2;
        if (check(mid)) {
            ans = mid;
            L = mid + 1;
        } else {
            R = mid - 1;
        }
    }

    cout << ans << endl;
}