Greedy Gift Takers

题目链接 题目大意 n头牛排队领礼物，每头牛有自己的ci，当它得到礼物后会插到倒数第ci个位置，问会有多少牛领不到礼物

输入: 一个 n<=1e5 每头牛对应的ci

分析: 这道题用二分来做,对位置进行二分,为什么可以用二分来做呢?分析问题，发现是由于队伍前面的一些数形成循环导致后面的数不可到达，这具有二段性.

怎么判二分的位置是不是可行的呢，就是取判断二分的mid能不能到到队首即可。记num为mid后面的数，如果ci<=num则num++(相当于移到后面去了),否则返回false,如果都满足就返回true. 可以发现的是尽管有些ci暂时插到mid之前，但是并不影响mid移到队首(如果本来就可以的话),所以就有一个贪心的想法，对mid前面的ci进行升序，更高效的处理.

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int maxn = 1e5+10;
int n;
int c[maxn],cc[maxn];

bool check(int x){
    for(int i = 1;i<=x;++i)cc[i]=c[i];
    sort(cc+1,cc+x);
    int num = n-x;//x后面一段的数量
    for(int i = 1;i<x;++i){//判断能不能移动到队首
        if(cc[i]<=num) num++;
        else return 0;
    }
    return 1;
}

int main(){
    ios;
    cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>c[i];
    }
    int l = 1,r = n;
    while(l<=r){
        int mid = (l+r)>>1;
        if(check(mid)) l = mid+1;
        else r = mid-1;
    }
    cout<<n-r;
    return 0;
}