题解 | #Greedy Gift Takers#

思路： 首先我们可以发现，如果第x个牛不能拿到礼物，则x之后的所有牛都不能拿到礼物，则区间具有单调性，可以想到用二分来解决 然后思考怎么写判断条件 我们需要知道一个结论： 怎么样会形成一个死循环呢？如果出现在前i个位置的牛多于i个，则这i个牛就会一直卡在这前i个位置，我们预处理出小于二分值位置的数量，判断每个位置i的牛是否多于i个，如果多于，证明二分答案大了，需要缩小右区间，反之则缩小左区间，直到找到答案位置为止。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
const int N = 100010;
int main()
{
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],a[i]=n-a[i];
    function<bool(int)> check = [&](int mid)->bool
    {
        int s[N]={0},sum=0;
        for(int i=1;i<mid;i++)s[a[i]]++;
        for(int i=1;i<mid;i++)
        {
            sum+=s[i];
            if(sum>=i)return true;
        }
        return false;
    };
    int l=0,r=n;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid))r=mid-1;
        else l=mid;
    }
    cout<<n-r<<endl;
}