Greedy Gift Takers

题目

有 N(1≤N≤10^51≤N≤10
5
)头牛按顺序排成一列,编号从 1 到 N,1 号牛在队头,N 号牛在队尾。

每次位于队头的牛 i 拿到一个礼物,然后插入到从队尾数c_ic
i
​ 头牛之前的位置。。举个栗子: 初始队列 1,2,3,4,5 c_1c
1
​ = 2,c_2c
2
​ = 3,则第一次操作后的序列为 2,3,1,4,5,第二次操作后的序列为 3,2,1,4,5。重复无限次操作,求最后有几头牛拿不到礼物。

输入输出格式

输入格式:
The first line contains a single integer, N

The second line contains NN space-separated integers c_1, c_2, \dots, c_Nc
1

2
​ ,…,c
N
​ .

输出格式:
Please output the number of cows who cannot receive any gifts.

输入输出样例

输入样例#1:
3
1 2 0
输出样例#1:
1

题解&&分析

最近做了好多的USACO的题…
看到这道题,最开始想到的就是纯模拟,但是这里礼物是无限的,我们也不清楚队列的变化规律
那么再想,如果第i个人(奶牛)拿不到礼物,那就是说前面的点成了一个循环,导致到不了的
那么第i+1个人也一定拿不到
所以考虑二分,现在就是求怎么算一个人前面的人是否成了一个循环
先想,如果第i个点确实拿不到,那么前面的点会一直循环,它们的c[]值一定会成为一个单调的
因为c[i]越大,它就在越前面
现在可以采用贪心的思想,我们可以把现在check的x前面的c按升序排序
如果c[i]越大,那么它就在越前面,也就会对x的位置影响越大
然后再一个一个排队即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 4;
int n;
int a[MAXN];
int b[MAXN];
bool check( int x ){
    memset( b , 0 , sizeof( b) ) ;
    for( int i = 1 ; i < x ; i ++ )
        b[i] = a[i];
    sort( b + 1 , b + x );
    int delta = n - x;
    for( int i = 1 ; i < x ; i ++ ){
        if( b[i] <=delta){
            delta ++;
        }
        else
            return 0;
    }
    return 1;
}
int main(){
    scanf( "%d" , &n );
    for( int i = 1 ; i <= n ; i ++ )
        scanf( "%d" , &a[i] );
    int l = 0 , r = n , ans;
    while( l <= r ){
        int mid = ( l + r ) / 2;
        if( check( mid ) )
            ans = mid , l = mid + 1;
        else
            r = mid - 1;
    }
    printf( "%d" , n - ans );
}

上一篇:英维克喜获2017“数据中心科技奖”最高奖项!


下一篇:嵌入式软件开发调试问题常用方法级案例分析