传送门

题意

更定n段长度为的木棍，问若把他们分成k个相同长度的，最大长度是多少

tags

• 二分

  分析

  可以对长度进行二分。二分下届为1，上界为max(a[i])。
  用贪心的方法经行检查。每个对于答案的贡献是。所以若说明mid的取值大了可以减少，否则需要增大。
  check函数复杂度：，总复杂度：

  参考代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 2e5 + 10;

int n, k;
int a[maxn];

bool check(int mid) {
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i] / mid;
    }
    return sum >= k;
}
int main(void) {
    FAST_IO;

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

    return 0;
}