680. 剪绳子

二段性：对于一个长度x，当长度x能够满足条件时，所有满足长度\(\le x\)的长度t，都能够满足条件，所以能够二分出长度的最大值。

实数二分，因为是实数，所以二分的终止条件不能用l < r来判断，而是应该根据题目要求的精度p令终止条件为r - l > 1e-(p + 2)。

复杂度：\(O(nlog(1e9))\)

#include<iostream>
using namespace std;

const int N = 100010;

int n, m;
int a[N];

int check(double mid){
    int sum = 0;
    for(int i = 0; i < n; i ++)
        sum += a[i] / mid;

    return sum >= m;
}

int main(){
    cin >> n >> m;

    for(int i = 0; i < n; i ++) cin >> a[i];

    double l = 0, r = 1e9;

    while(r - l > 1e-4){
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf", l);

    return 0;
}

680. 剪绳子

原文：https://www.cnblogs.com/tomori/p/14299959.html