Acowdemia (USACO Silver 2021 Open)

$N\lt 10^5$ 篇文章， $K \lt 10^5$ 篇综述，每篇可以将 $L$ 篇文章的引用次数提升1。问指数 $h$ 最高是多少（指数 $h$ 的定义：至少有 $h$ 篇引用次数不少于 $h$ ）

$h$ 这样的定义，不太好直接求，但是容易验证，指向这可能是个二分答案的题目。我们试着验证一个 $h$ 是否可行：

首先对 $c[i]$ 从大到小排序，满足条件的论文，肯定是原来的引用数越多越好，所以取前面的 $h$ 篇论文验证就行了。
如果 $c[i] < h$ ，则需要用综述提升 $h - c[i]$ 次。如果这个次数大于 $K$ ，则无解，因为每篇综述只能引用这篇论文一次，所以所有综述能提升某一论文的引用次数总和不超过 $K$ 。
在 $h - c[i] \leq K$ 的情况下，我们观察可以发现，实际上综述对于引文数的提升是可以随意分配的（举几个例子试一下就知道了），所以此时只要保证引文总的缺口小于等于 $K \times L$ 即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, k, l;
int c[100005];
 
bool check(int h) {
    ll r = (ll)k * l;
    for (int i = 0; i < h; i++) {
        if (c[i] + k < h) return false;
        if (c[i] < h)
            r -= (h - c[i]);
    }
    return r >= 0;
}
 
int main() {
    scanf("%d %d %d", &n, &k, &l);
    for (int i = 0; i < n; i++)
        scanf("%d", &c[i]);
    sort(c, c+n, greater<int>());
 
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    printf("%d\n", lo);
    return 0;
}