Ropes

題目

有 $n$ $(1 \leq n \leq 10000)$ 條繩子，第 $i$ 條長度為 $a_i$ $(1 \leq a_i \leq 10^7)$，你需要從這些繩子他們剪成 $k$ $(1 \leq k \leq 10000)$ 條等長的線段，請問剪出來的線段最長可以多長？

解題思路

這題沒有辦法直接從輸入算出答案。雖然答案是浮點數，沒辦法直接枚舉，但是我們可以「二分搜答案」。

但是，在確認能二分搜答案之前，我們要先確定答案是否有「單調性」。對於每一個 $x$，如果用長度 $x$ 沒有辦法切成 $k$ 段以上，長度比 $x$ 大就更不可能切 $k$ 段。如果可以用長度 $x$ 把繩子切成 $k$ 段，那比 $x$ 小的長度也一定可以。

更精確來說，對於每一個 $m$，我們可以把每一條繩子的 (長度除以 $m$) 加起來，在確認總和 (代表能夠分割成幾段) 是否大於等於 $k$，用此資訊縮小二分搜的範圍。這個演算法的時間複雜度是 $O(Nlog(max(a_i)))$ ，可以通過這題。

常見錯誤

• 記得加 setprecision，不然會 WA on test 9
• 浮點數二分搜不要加 $(l = m + 1)$ 或 $(r = m - 1)$，不然可能會剛好跳過答案。

完整程式碼

#include <bits/stdc++.h>

using namespace std;
 
#define int long long
 
signed main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    double l = 0, r = 1e7;
    for (int j = 0; j < 100; j++) {
        double m = (l + r) / 2;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += floor((double)(a[i]) / m);
        }
        if (cnt >= k) {
            l = m;
        }
        else {
            r = m;
        }
    }
    cout << setprecision(7) << l << "\n";
}