2019-2020 ICPC, NERC, Southern and Volga Russian Regional Contest J. The Parade(二分+贪心)

题目链接
大意：给你一个组士兵，告诉你身高 $i$i的人数 $a_i$ai​，让你放在 $k$k行，使得每行人数相同且每行中士兵身高差不超过 $1$1，问你最多能放多少士兵满足条件。
思路:二分每行人数。证明：如果 $x$x满足的话，显然可以把每行都去掉相同的人数使得 $[1,x]$[1,x]都满足。
遍历 $n$n个人，先把上一个身高的士兵没用完的看能不能和当前身高的放满一行，再放当前身高的。
如果最后放的行数比 $k$k大，那么当前值即满足。
细节见代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int t, n;
LL k, a[N];

int main() {
    ios::sync_with_stdio(false);
    for (cin >> t; t; t--) {
        cin >> n >> k;
        LL s = 0;
        for (int i = 1; i <= n; i++)cin >> a[i], s += a[i];
        LL l = 1, r = s / k, ans = 0;
        while (l <= r) {
            LL mid = l + r >> 1, now = 0, last = 0;
            for (int i = 1; i <= n; i++) {
                LL re = a[i];
                if (re + last >= mid) {//先看能不能把剩下的用掉
                    re -= mid - last;
                    now++;
                }
                LL x = re / mid;
                now += x;
                LL y = re % mid;
                last = y;
            }
            if (now >= k)ans = mid, l = mid + 1;
            else r = mid - 1;
        }
        cout << ans * k << '\n';
    }
    return 0;
}