[USACO 2017 Dec P]Greedy Gift Takers

一、题目描述

共有N头牛按顺序排成一列,编号从1到N,1号牛在队头,N号牛在队尾.每次位于队头的牛i拿到一个礼物后,然后插入到从队尾数ci头牛之前的位置.举个栗子来说吧:初始队列 1,2,3,4,5 c1=2,c2=3，则第一次操作后的序列2,3,4,1,5,第二次操作后的序列为 3,2,4,1,5.重复无限次操作,求最后有几头牛拿不到礼物。

输入格式：

The first line contains a single integer,N.

The second line contains NN space-separated integers c1,c2,...,cN.

输出格式：

Please output the number of cows who cannot receive any gifts.

二、解题分析

又到了饭后闲聊时间了,哈哈哈.其实刚开始看到这道题的时候,主要是被这个牛插队的、插队的给搞懵了,这题如果不是雨巨把这题放在二分那块专题,我可能一开始不会往二分这方向想,但其实当你思考一段时间后,还是会认为这道题用二分来做还是会比较好做的.

该题主要有三个思维小难点：

①当有一头牛始终都拿不到礼物时,那么其后面的所有牛也肯定都拿不到礼物了,这个首先是第一点要想明白的.

②与此同时,第二个难点就来了,如何确定前i头牛陷入了死循环了呢?这个其实我也是参考了别人的博客才想通的,先假设第x头牛拿不到礼物,其前面的x - 1头牛都能拿到礼物,那么在位置x陷入死循环的条件时当且仅当前x - 1个位置上的牛的个数大于x - 1时,这x头牛就会陷入死循环.

③那么该题为啥能用二分呢?我们可以一起来思考一下,当我们二分出来的答案>真实值的时候,此时肯定不会满足题意;当我们二分出来的答案<=真实值的时候，此时就满足题意,符合单调性,因此可以进行二分来出答案.

想明白这三点,其实基本上这题就可以AC了.

三、AC代码

using namespace std;

int n,c[100010],cnt[100010]; //cnt数组记录前i个位置的牛的个数
bool judge(int x){
    int sum = 0;
    memset(cnt,0,sizeof(cnt)); //注意cnt数组是定义在全局范围内,注意清0操作
    for (int i = 1;i < x;i++) cnt[c[i]]++;
    for (int i = 1;i < x;i++){
        sum += cnt[i];
        if (sum >= i) return true;
    }
    return false;
}
int main(){
    scanf("%d",&n);
    int l = 0,r = n;
    for (int i = 1;i <= n;i++){
        scanf("%d",&c[i]);
        c[i] = n - c[i]; //数据预处理
    }
    while (l <= r){
        int mid = (l + r) / 2;
        if (judge(mid)) r = mid - 1;
        else l = mid + 1;
    }
    cout << n - r;
    
    return 0;
}