NC23049

华华给月月准备礼物

题解

显然可以二分答案解决。

二分答案证明

令 表示裁剪为长度 的根数，

因此 具有单调性，可以二分答案解决。

Code

#include<bits/stdc++.h>
using namespace std;

const int maxn = 200000 + 7;

int n, k, L = 1, R = 1000000000;
int mid , ans;

int a[maxn];

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

int main(void) {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    while(L <= R) {
        mid = (L + R) >> 1;
        if(check(mid)) ans = mid, L = mid + 1;
        else R = mid - 1;
    }
    printf("%d\n", ans);
    return 0;
}