Greedy Gift Takers(二分，贪心）

贪心）"/>

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;}