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

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接

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

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

参考代码：

/*
二分思维训练：
枚举值，判断是否可行，求出最大...最小值
*/
#include <cstdio>
#include <algorithm>
#define mid ((double)(l + r) / 2)
using namespace std;const int maxn = + , INF = ;
int n, k;
double value[maxn];bool check(double c) {
int num = ;
for(int i = ; i < n; i ++) {
num += (int)(value[i] / c);
}
return num >= k;
}int main() {
while(~scanf("%d %d", &n, &k) && (n + k) != ) {
for(int i = ; i < n; i ++) {
scanf("%lf", &value[i]);
}
double l = , r = INF;
for(int i = ; i < ; i ++) {//进行100次二分，可以保证将解求出，并且可以很大限度保证高精度，由于double型和int型不同，需要用高精度辅助二分结束条件，所以一般卡一个不太大的二分次数上限即可完美求解
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2f\n", double(l));
}
return ;
}