模拟赛 T1 好做法

不服来叉

首先肯定要二分答案 \(k\)，然后肯定留最大的 \(k\) 个数，

考虑删除剩下 \(n-k\) 个数的策略，肯定是倒着删，考察一下删除倒数第 \(i\) 个数的时候到底发生了什么，

这里我们先假设之前 \(i-1\) 个数可以成功删掉，否则可以在前面判断出不能删，

不妨考虑在删之前 \(i-1\) 个数的时候，如果 \(x\) 有法力值分给了这 \(i\) 个数中的 \(k\)，视为 \(x\) 向 \(k\) "进了一位"，

那我们就要使得之前 \(i-1\) 个数对 \(i\) 的"进位"，也就是分给 \(i\) 的法力值尽量少，

显然有策略：对每个数 \(x\)，先把法力值分给所有不会产生进位的 \(n-i\) 个数，剩余的法力值留下来进位，

可以看成是填一个 \(i\) 行 \(n-i\) 列的矩阵，每次填一行，多余的法力值留到之后的行，

那这样留到最后一行的进位个数就是 \(\sum\limits_{x=1}^{i-1}v_x-(i-1)(n-i)\)，

那么 \(i\) 需要分出去的法力值就是 \(v_i\) 加上进位，也就是 \(\sum\limits_{x=1}^iv_x-(i-1)(n-i)\)，

\(i\) 只能把法力值分给剩下 \(n-i\) 个数，所以 \(\sum\limits_{x=1}^iv_x-(i-1)(n-i)\le n-i\)，如果满足条件那 \(i\) 就能被删掉，否则 \(i\) 删不掉。

#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int T, n, a[5000050];
inline int R()
{
    int q = 0;
    char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        q = q * 10 + c - '0', c = getchar();
    return q;
}
bool C(int k)
{
    int z = 0;
    for (int i = n; i > k; --i)
    {
        z += a[i - k];
        if (z > (n - i + 1) * (i - 1))
            return 0;
    }
    return 1;
}
signed main()
{
    freopen("magic.in", "r", stdin);
    freopen("magic.out", "w", stdout);
    T = R();
    while (T--)
    {
        n = R();
        for (int i = 1; i <= n; ++i)
            a[i] = R();
        sort(a + 1, a + n + 1);
        int l = 1, r = n;
        while (l <= r)
        {
            int m = l + r >> 1;
            if (C(m))
                r = m - 1;
            else
                l = m + 1;
        }
        printf("%lld\n", l);
        for (int i = 1; i <= n; ++i)
            a[i] = 0;
    }
    return 0;
}