POJ-1064.Cablemaster.(二分法枚举值求最优值)

时间:2022-10-27 16:36:59

 题目链接

本题大意:给你n个长度为value[ i ]的长木板,让你切割成为等长的k份,问你切割的最大长度是多少。

本题思路:其实很容易可以想到先找到一个上界和一个下界,开始枚举里面的所有长度,取最长的那个即可,此时发现长度为浮点型朴素算法自然无法枚举,我们可以想到二分,局部逼近即可。

参考代码:

/*
    二分思维训练:
        枚举值,判断是否可行,求出最大...最小值
*/
#include <cstdio>
#include <algorithm>
#define mid ((double)(l + r) / 2)
using namespace std;

const int maxn = 10000 + 5, INF = 100000;
int n, k;
double value[maxn];

bool check(double c) {
    int num = 0;
    for(int i = 0; i < n; i ++) {
        num += (int)(value[i] / c);
    }
    return num >= k;
}

int main() {
    while(~scanf("%d %d", &n, &k) && (n + k) != 0) {
        for(int i = 0; i < n; i ++) {
            scanf("%lf", &value[i]);
        }
        double l = 0, r = INF;
        for(int i = 0; i < 100; i ++) {//进行100次二分,可以保证将解求出,并且可以很大限度保证高精度,由于double型和int型不同,需要用高精度辅助二分结束条件,所以一般卡一个不太大的二分次数上限即可完美求解
            if(check(mid)) l = mid;
            else r = mid;
        }
        printf("%.2f\n", double(l));
    }
    return 0;
}