本文主要是介绍POJ 1064 Cable master （二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=1064
题意：N条绳子，长度分别为Li。若从中切割出K条长度相同的绳子，这K条绳子每条最长能有多长。
二分查找，下界为0上界为最大的L，答案不能四舍五入。
用C++可以过，G++WA。。。为什么。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-6
using namespace std;
int n, k;
double L[10010];
int check(double x) {int cnt = 0;int i;for(i = 0; i < n; i++) {cnt += int(L[i] / x);}if(cnt >= k) return 1;else return 0;
}
int main() {scanf("%d %d", &n, &k);int i;double maxl = 0;for(i = 0; i < n; i++) {scanf("%lf", L + i);maxl = max(maxl, L[i]);}double l = 0, r = maxl;while(r - l > eps) {double mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}printf("%.2lf\n", floor(r * 100) / 100);return 0;
}这篇关于POJ 1064 Cable master （二分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
