题意:

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


题解:

首先假设x为最后答案,那么显然我们能够判断x是否成立(贪心将每个圆木棍 分成长度为x的小木棍看是否>=k),
并且ans有着明显的单调性,所以直接二分就可以了


代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head

int _,n,m,k,a[maxn],b[maxn],c[maxn];

bool ok(int x){
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=a[i]/x;
        if(ans>=k) return 1;
        //cout<<x<<','<<ans<<endl;
    }
    return 0;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l=1,r=1e9,ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(ok(mid)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    printf("%d\n",ans);
}