华华给月月准备礼物

骑猪看日落 2022-03-10 13:19 278阅读 0赞

时间限制：C/C++ 1秒，其他语言2秒  
空间限制：C/C++ 32768K，其他语言65536K  
64bit IO Format: %lld

## 题目描述  ##

二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。  
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？

## 输入描述: ##

第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
    第二行N个正整数LiLi表示每根木棍的初始长度。

## 输出描述: ##

输出一行一个非负整数表示每根木棍的最大长度。

示例1

## 输入 ##

复制

5 10
    4 4 4 5 3

## 输出 ##

复制

## 说明 ##

如果长度为2，只能得到2+2+2+2+1=9根，不够；长度为1可以得到4+4+4+5+3=20根，足够。所以答案最大是1。

示例2

## 输入 ##

复制

5 3
    1 2 3 4 5

## 输出 ##

复制

## 备注: ##

1≤N≤2×10^5，1≤Li≤10^9，1≤K≤10^9

题解：二分木棍长度，l=1,r=输入最长的长度，然后和的平均是否大于k。

#include<bits/stdc++.h>
    using namespace std;
    int n,k,a[100010],l=1,r,maxn;
    int sum(int m)
    {
        int s=0;
        for(int i=0;i<n;i++)
            s+=a[i]/m;
        return s>=k;
    }
    int main()
    {
        cin>>n>>k;
        for(int i=0;i<n;i++)
            cin>>a[i],maxn=max(a[i],maxn);
            r=maxn,maxn=0;
            while(l<=r)
            {
                int m=(l+r)>>1;
                if(sum(m))
                {
                    maxn=m;
                    l=m+1;
                }
                else r=m-1;
            }
        cout<<maxn<<endl;
        return 0;
    }