【acwing 寒假每日一题】day6剪绳子

题目来源：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
样例解释
第一根和第三根分别裁剪出一根2.50长度的绳子，第二根剪成2根2.50长度的绳子，刚好4根。

思路

直接求最大长度不好求，但是判断某个长度x是否能够达到要求 还是好求的(直接每根绳子的长度/x 然后累加一下 达到题目要求的数量了 就是满足的 反之就是不满足的)
那么 我们可以采取二分 因为二分的本质就是 把一个最优化问题转换成一个判定问题
继续考虑能否根据中点，将区间缩小一半
当中点达到要求了 那么中点左边的点应该都可以，但是我们找的是最大值 我们应该在右区间找
如果中点没有达到要求，那么中点右边的点应该都是不行的 我们应该在左区间找
那么我们写一遍浮点数二分的板子就行了

小tip 浮点数二分的精度

浮点数二分 区间长度小于一个很小的数的时候 就认为找到答案了

1. 经验告诉我们这个数一般取1e-(k+2) k是题目要求保留的位数，如此题就是1e-4
2. 使用1e7去除以check函数的时间复杂度得到循环次数
   将while循环改为for循环，如此题1e7/1e5就是100

代码

while循环

#include<bits/stdc++.h>

using namespace std;

const int N=100010;
int n,m;
int w[N];

//判断x是否满足条件
bool check(double x)
{
    int cnt=0;
    //计算每一根绳子能够剪裁出多少根长度为x的绳子
    for(int i=0;i<n;i++) cnt+=w[i]/x;
    //至少要满足基本要求 即至少能够剪裁出m根绳子
    return cnt>=m;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>w[i];
    double l=0,r=1e9;
    while(r-l>=1e-4)
    {
        double mid=(l+r)/2;
        //满足条件的话 最大值应该在右边区间了
        if(check(mid)) l=mid;
        //不满足条件的话 最大值只可能在左边区间了
        else r=mid;
    }
    printf("%.2f",r);
    return 0;
}

for循环

#include<bits/stdc++.h>

using namespace std;

const int N=100010;
int n,m;
int w[N];

//判断x是否满足条件
bool check(double x)
{
    int cnt=0;
    //计算每一根绳子能够剪裁出多少根长度为x的绳子
    for(int i=0;i<n;i++) cnt+=w[i]/x;
    //至少要满足基本要求 即至少能够剪裁出m根绳子
    return cnt>=m;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>w[i];
    double l=0,r=1e9;
    for(int i=0;i<200;i++)
    {
        double mid=(l+r)/2;
        //满足条件的话 最大值应该在右边区间了
        if(check(mid)) l=mid;
        //不满足条件的话 最大值只可能在左边区间了
        else r=mid;
    }
    printf("%.2f",r);
    return 0;
}