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";
}