【每日一题】华华给月月准备礼物（二分答案）

Solution
二分答案模板题。
先给出俺的万能二分模板： (ans为答案且注意初始化为0，其他只要改一下check函数就可以用于其他题)

ll l=1,r=max,ans=0;
while(l<=r){
    ll mid=l+r>>1;
    if(check(mid)) ans=mid,l=mid+1;
    else r=mid-1;
}

这道题的话就是直接枚举木棍的长度，然后判断切出的数目是否大于等于k。

Code

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;

const int manx=2e5+5;

ll a[manx]; ll n,k;

bool check(ll x){
    ll cnt=0;
    for(int i=1;i<=n;i++)
        cnt+= a[i]/x;
    return cnt>=k;
}

int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++) a[i]=read();
    ll l=1,r=1e9,ans=0;
    while(l<=r){
        ll mid= l+r>>1;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}