NC23049

题意

你有段小木棍，对每段小木棍切割，要求得到段长度相等为(正整数)的小木棍，求最大为多少？

思路

答案具有单调性，故考虑二分，时间复杂度

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e5 + 5;

int n,k,a[N];

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int L=1,R=a[n]+1,ans=0;
    while(L<R){
        int mid=L+(R-L)/2;
        if(check(mid)) L=mid+1,ans=mid;
        else R=mid;
    }
    cout<<ans<<'\n';
    return 0;
}