POJ - 1064

题意

有N条绳子, 他们的长度分别为 Li . 如果从它们中切割出K条长度相同的绳子的话, 这K条绳子每条最长能有多长? 答案保留到小数点后两位.

解法1(二分搜索)

分析

定义check函数:

check(x): floor( Li /x)的总和是否不小于K. (一般情况下最大化问题设为”不小于”, 最小化问题设为”不大于”.)

这道题需要注意的是输出的处理, 假如我们用%.2f直接输出r, 那么会WA, 因为%.2对r的小数点第三位的处理是四舍五入. 此外, 用二分搜索处理这种答案为小数的问题时, 要注意误差. 建议直接for循环个100次, 这样子得出来的答案可以达到 10−30 的精度范围, 基本是没有问题的.

代码

#include<set> #include<map> #include<cmath> #include<queue> #include<cctype> #include<cstdio> #include<vector> #include<string> #include<sstream> #include<cstdlib> #include<cstring> #include<float.h> //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON #include<limits.h> //INT_MAX,LLONG_MAX #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const double PI = acos(-1.0); #define INF 0x3f3f3f3f int N, K; double L[10009]; bool check(double x){ int num=0; for(int i=0; i<N; i++){ num+=floor(L[i]/x); } return num>=K; } int main(void){ //freopen("in", "r", stdin); //freopen("out", "w", stdout); scanf("%d%d", &N, &K); for(int i=0; i<N; i++) scanf("%lf", L+i); double l=0, r=INF; for(int i=0; i<100; i++){ double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.2f\n", floor(r*100)/100); return 0; }