题解 P4090

· · 题解

P4090 题解

代码别的题解都贴出来了，这里主要补充讲解一下思路。

结论1      最终的情况必然是整个序列被分成两部分，前一部分进入循环并且获得礼物，后一部分在循环之外，没有礼物。

（即最前面进入循环中的牛必然拿到礼物，后面的牛必然拿不到礼物）

未进入循环的牛显然无法到达第一个位置，因而拿不到礼物。

结论2      第 \boldsymbol{n} 头牛至少在第 \boldsymbol{n} 次时拿到礼物。

由于每次变换后，对于除了这次拿到礼物的牛外其他的牛，要么它的位置前进一个空位(拿到礼物的牛移到了它后面)，要么保持原地不动(拿到礼物的牛移到了它前面)。因此在第 n 次之前，第 n 头牛不可能拿到礼物。

接下来讲讲算法的具体步骤。由结论1可以发现满足单调性，因此使用二分查找，假定牛k是最后面能拿到礼物的牛，判断是否可行。

然后我们面临的问题就是如何判断前面的牛能否进入循环？

int check(int k){
    for(int i=1;i<k;i++){
        b[i]=a[i];
    }//将所需要的数组复制一份
    sort(b+1,b+k);//排序
    int bound=n-k;
    for(int i=1;i<k;i++){
        if(b[i]>bound) return 0;
        bound++;
    }
    return 1;
}

由上面的结论不难看出，一头牛是否在循环中，只与它前面的牛有关。牛 k 能够到达第一，说明前面所有的牛都会到牛 k 的后方，将其挤到第一位。

而我们假定牛 k 及前面所有的牛都会到达第一并重新归队，所以在我们的假设中每头牛不论顺序如何都会到达牛\boldsymbol{k}后方。然后我们用贪心，优先让新位置靠后的牛先入队，尽量把牛 k 往前挤。

每次一头牛到达后方，能把牛 k 往前挤的位置范围就扩大了，因此bound++ 。而如果发现这头牛无法把牛 k 往前挤，即 b[i]>bound ，那么牛 k 就不可能再前进到达第一位了，因为排序之后的牛的新位置只可能在更前面,于是 return 0; 。而如果牛 k 前方所有的牛都能顺利到达它的后面，则牛 k 能够到达第一位,故return 1; 。

题解就到此为止了，欢迎补充和纠错~☆

完