题解

本题使用二分答案 + 贪心验证求解礼物分配问题。

算法思路：

1. 二分答案：

   • 二分最终能够拿到礼物的奶牛数量 $k$
   • 答案范围：$[0, n-1]$（至少有1头奶牛拿不到礼物）
   • 目标：找到最大的 $k$ 使得有 $k$ 头奶牛能拿到礼物

2. 验证函数（check）：

   • 假设有 $k$ 头奶牛拿到礼物，则剩余 $m = n - k$ 头奶牛没有拿到
   • 将这 $m$ 头奶牛的贪婪值从大到小排序
   • 贪心判断：对于排序后的第 $i$ 头奶牛（贪婪值为 $b[i]$）：
     • 它在原序列中排名为 $n - b[i] + 1$
     • 如果 $n - b[i] + 1 \leq i$，说明这头奶牛能够"挤掉"前面的某头奶牛
     • 若存在任何一头奶牛满足该条件，说明方案矛盾，返回失败

3. 贪心正确性：

   • 贪婪值越大的奶牛，越可能在后续轮次中拿走礼物
   • 如果某头没拿到礼物的奶牛其贪婪值排名 $\leq$ 它在"没拿到"序列中的位置，则它可以替换掉某个已经拿到礼物的奶牛
   • 按贪婪值从大到小检查，确保最有可能"反击"的奶牛被优先考虑

4. 答案输出：

   • 二分找到最大的可行 $k$ 值

时间复杂度：$O(n \log^2 n)$，其中排序 $O(n \log n)$，二分 $O(\log n)$。

#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

inline int read() {
        int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
        while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x;
}

const int N = 1e6 + 5;

int n, a[N], b[N];

inline int check (int k) {
        int m = n - k;
        rep (i, 1, m) b[i] = a[i];
        sort (b + 1, b + 1 + m, [&] (int x, int y) { return x > y; } );
        rep (i, 1, m) {
                if (n - b[i] <= i) return 1;
        }
        return 0;
}

signed main() {
        n = read ();
        rep (i, 1, n) a[i] = read ();

        int l = 0, r = n - 1, m = 0;
        while (l <= r) {
                m = (l + r) >> 1;
                if (check (m)) l = m + 1;
                else r = m - 1;
        }
        cout << r << endl;
        return 0;
}