AcWing 680. 剪绳子

680. 剪绳子

有 N 根绳子，第 i 根绳子长度为 Li，现在需要 M 根等长的绳子，你可以对 N 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 M 根绳子最长的长度是多少。

输入格式

第一行包含 2 个正整数 N、M，表示原始绳子的数量和需求绳子的数量。

第二行包含 N 个整数，其中第 i 个整数 Li 表示第 i 根绳子的长度。

输出格式

输出一个数字，表示裁剪后最长的长度，保留两位小数。

数据范围

1≤N,M≤100000,
0<Li<109

样例输入

3 4
3 5 4

样例输出

2.50

题意

给定绳子数和需求数，求满足需求的最长裁剪长度

思路

• 1.数据范围10的9次方，暴力会超时
• 2.根据样例输出，答案是浮点数，可想到浮点数二分
• 3.裸浮点数二分模板题了
• 4.如果你不知道二分请点击

坑点

• 1.左边界需从0开始，最小长度不能够作为左边界
• 2.二分需要满足单调性

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
double num[100005]; 
int qiuhe(double x)//求和，当前长度可以剪成多少段 
{
    int sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=int(num[i])/x;//强制类型转换后进行计算 
        //printf("%d\n",sum);
    }
    return sum;
}

double erfen(double l,double r)//求出满足条件的最长长度 
{
    while(1)
    {

        double mid=(l+r)/2;
        //printf("%lf %lf %lf %d\n",mid,l,r,qiuhe(mid));
        if(qiuhe(mid)<m)//剪的数量太少，剪的长度需要变短 
        {
            r=mid; //缩小右区间 
        }else{
            l=mid;//缩小左区间 
        }   
        if(r-l<0.001)//浮点数二分，当误差小于一定程度时，我们认为找到了答案 
        {
            break;
        }   
    }
    return l;
}

int main()
{
    //精度问题，可以使用浮点数二分 
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        scanf("%lf",&num[i]);
    }
    sort(num,num+n);
    printf("%.2lf",erfen(0,num[n-1]));
    return 0;
}

总结

浮点数二分模板题，适合练手，据说是头条的笔试题