Greedy Gift Takers(二分，贪心）

[USACO17DEC] Greedy Gift Takers P - 洛谷

分析：

（鬼知道我看了多少人的题解）

由于可以操作无限次，必存在递增的情况

所以我们对于当前[1,mid)的奶牛按照c值排序之后

贪心的先放c中最小的奶牛

如果依然存在一头奶牛被放在mid之前

那么就无法使mid得到礼物

源代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll c[100005];
ll cnt[100005];
ll n;
bool check(ll x)
{
    if(x==1)return 1;
    ll b[n+1];
    ll limit=n-x;
    for(ll i=1;i<x;i++)b[i]=c[i];
    sort(b+1,b+x,[](ll x,ll y){return x<y;});
    for(ll i=1;i<x;i++)
    {
        if(b[i]>limit)return 0;
        limit++;
    }
    return 1;
}
void solve()
{
  cin>>n;
  for(ll i=1;i<=n;i++)
  {
      cin>>c[i];
  }
  ll l=0,r=n+1;
    ll md=-1;
  while(l<=r)
  {
      ll mid=l+(r-l)/2;
      if(check(mid))
      {
          md=mid;
          l=mid+1;
      }
      else r=mid-1;
  }
    cout<<n-md<<'\n';
}
    int main()
   {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--)
    solve();
    return 0;
    }