【挑战程序设计竞赛】 二分法

发表于

描述
n条绳子，第i条绳子长度为a[i],切割成长度相同的k段，求能切割出最大的长度

样例

1
2
输入: n = 4;  k =11 a = {8.02,7.43,4.57,5.39};
输出: 2.00 (每条绳子分割可以得到4条，3条，2条，2条，共11条绳子)

思路
将这题转化为求满足 C(x) 的最大的 x,解范围下界是个较小的可行解，上界是一个较大的不可行解，每次取中间值缩小解范围。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool C(vector<double> a,int K,double x) {
    int len = a.size();
    int sum = 0;
    for (int i = 0; i < len; i++) {
        sum += int(a[i] / x);
    }
    return sum >= K;
}

void solve(vector<double> a, int K) {
    double lo = 0;                //下界，显然0是可行解，但很不优，需要向上扩充
    double hi = 10000;            //上界，不可行解，需要向下收缩
    //循环100次是为了尽量缩小解的范围
    for (int i = 0; i < 100; i++) {
        double mid = lo + (hi - lo) / 2;
        if (C(a, K, mid)) { lo = mid; }
        else { hi = mid; }
    }
    printf("%.2lf", lo);
}