二分搜索 POJ 1064 Cable master

题目传送门

 /*
题意:n条绳子问切割k条长度相等的最长长度
二分搜索:搜索长度,判断能否有k条长度相等的绳子
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std; const int MAXN = 1e4 + ;
const int INF = 0x3f3f3f3f;
double w[MAXN];
int n, k; int check(double len) {
int ret = ;
for (int i=; i<=n; ++i) {
ret += (int) (w[i] / len);
}
return ret;
} int main(void) { //POJ 1064 Cable master
//freopen ("POJ_1064.in", "r", stdin); while (scanf ("%d%d", &n, &k) == ) {
for (int i=; i<=n; ++i) {
scanf ("%lf", &w[i]);
}
double l = , r = 1e9;
for (int i=; i<=; ++i) {
double mid = (l + r) / ;
if (check (mid) >= k) l = mid;
else r = mid;
}
printf ("%.2f\n", floor (l * ) / );
} return ;
}
上一篇:配置安卓运行环境/安卓sdk


下一篇:[原创]obj-c编程15[Cocoa实例02]:KVC和KVO的实际运用