题目地址:http://poj.org/problem?id=1064

题目:


给n条线段,单位为米,要对这些线段裁剪,剪出m条等长的线段,且使这些线段尽可能地长,结果要精确到厘米,即小数点后两位。不能小于1厘米,小于1厘米要输出0.00 

 

解题思路:


最大值,最小值之间二分处理,不断缩小区间范围,确定最终解。

注意在判断是否小于0.01m时,不能直接和0.01比较,浮点比较会出现误差,可以先*100,取整数部分,再/100(保留两位小数)

如0.012  0.012*100=1.2 取整=1.0, 1.0/100 = 0.01

如0.0099 0.0099*100=0.99 取整=0.0  0.0/100=0.00

⚠️G++double的输出格式是%f,C++double的输出格式是%lf

 

ac代码:


#include <iostream>
#include <cmath>
#include <string.h>
#include <stdio.h>
using namespace std;
const int maxn = 10005;
int k, n;
double a[maxn];
bool judge(double mid)
{
    int sum = 0;
    for(int i = 1; i <= n; i++)
    {
        sum += int(a[i] / mid);
    }
    return sum >= k;
}
int main()
{
    scanf("%d %d",&n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%lf", &a[i]);
    double l = 0, r = 100005; // 长度1m-100km
    for(int i = 1; i < 200; i++)
    {
        double mid = (l + r) / 2;
        if(judge(mid)) l = mid; //缩小范围,求的最大的满足条件的解
        else r = mid;
    }
    printf("%.2lf\n", floor(l*100)/100);
    return 0;
}