AcWing寒假每日一题——Day6剪绳子

680剪绳子

一、题目描述

有 N 根绳子，第 i 根绳子长度为   L i \ L_i  Li​，现在需要M根等长的绳子，你可以对 N 根绳子进行任意裁剪（不能拼接），请你帮忙计算出这 M 根绳子最长的长度是多少。
输入格式
第一行包含2个正整数N、M，表示原始绳子的数量和需求绳子的数量。
第二行包含N个整数，其中第 i 个整数   L i \ L_i  Li​表示第 i 根绳子的长度。
输出格式
输出一个数字，表示裁剪后最长的长度，保留两位小数。
数据范围
1≤   N , M \ N,M  N,M≤100000,
0<   L i \ L_i  Li​<   1 0 9 \ 10^9  109
输入样例

3 4
3 5 4

输出样例

2.50

样例解释：
第一根和第三根分别裁剪出一根2.50长度的绳子，第二根剪成2根2.50长度的绳子，刚好4根。

二、问题分析

  我们可以将问题转化为在一段区间内求满足题意的绳子的最大值。，本题用到了浮点数的二分法。
代码如下（示例）：

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int q[100010];
bool check(double mid)//判断是否满足题意，即所有情况的和>=要求的m个数
{
    int cnt=0;
    for(int i=0;i<n;i++)
        cnt+=q[i]/mid;
    return cnt>=m;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>q[i];
    double l=0,r=1e9;//二分的左边界与右边界，即0和最大绳长
    while(r - l > 1e-4)//因为题目要求保留两位小数，所以r与l的距离小于1e-4即可
    {
        double mid=(l+r)/2;
        if(check(mid))l=mid;//如果mid满足条件说明，最长绳长在mid右边，将左边界l调整为mid即可
        else r=mid;//同理
    }
    printf("%.2lf\n",r);//输出r或l都可
    return 0;
}