题解：[USACO 2017 Dec P]Greedy Gift Takers

没想到第一次题解是因为喉咙疼，说不了话，很烦引入正文：一眼过去题目英文昏=。=

大概意思就是牛牛排队领东西，领好东西就排到最后，但是有坏牛牛会跑到插队每头奶牛收到礼物后可以选择向队尾的某些奶牛插队，而不是必须排在队尾。插到倒数第ci头，然后问有多少有多少可怜的牛牛领不到东西（无限发礼物哦，羡慕牛牛有无限的东西领）

有一说一这玩意有点昏，但是我们换个角度想一想倒数第ci 不就是插到 n - ci的位置。

如果有牛牛领不到礼物的话，那么显然后面的牛牛肯定也领不到东西的啦。所以我们只要找那个位置的牛牛领不到东西就可以啦，同理那个位置前面有牛牛无限领东西了，不然后面的牛牛也不至于领不到东西

假设第一头领不到东西的牛牛的位置在第x，那么在x之后的前面存在有牛牛可以无限领东西（有点绕）,符号表示的话就是c1,c2..cx - 1的牛牛还没有无限循环，但是到cx 的时候有循环了，有牛牛领不到东西了，c1 到 cx有循环，那么c1,c2,..cx + 1 肯定也有循环的啦那么只要找到x的位置就可以啦，我们就可以通过二分找x的位置，毕竟选的位置在x前就无循环，选的在x之后就有循环。

那么问题就还剩下怎么找出有无限循环的牛圈（莫名想到莫比乌斯环），其实这个条件挺好想的前i个位置至少i有头牛，就比如说样例给1，2，0，然后这些牛去的位置就是2，1，3;前面两个位置就有2个牛就可以无限循环了，在比如给个1，1，0，去的位置就是2，2，3，前2个位置就有2个牛就可以无限循环了，在比如给2，1，0;去的位置就是1，2，3，注意这时候是第一个牛就形成了循环，因为第一头牛拿了又去了第一个位置，就一直是他拿；

那么第一部分就是

 int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        int t;
        cin >> t;
        a[i] = n - t;
    }
//直接记录每天牛拿完去哪里就可以了

第二部分就是二分部分啦上板子

 int l = 1 , r = n;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid; 
      //1到第mid头有循环，那么我们不就缩小边界
        else l = mid + 1; 
      //无循环就扩大边界
    }
   cout << n - r;
	//r是找到的循环的边界输出就可以了

最后就是重点部分check 找循环可以前缀和一下，关于我这个**写了一堆特判，然后在干饭的时候灵感一现发现前缀和就可以了（食物的力量）

for(int i = 1 ; i <= mid ; i ++){
        b[a[i]]++; 
    }
    //再开一个数组去记第i个位置会出现几头牛

然后就是找循环啦

for(int i = 1 ; i <= mid ; i ++){
        b[i] += b[i - 1];
        if(b[i] >= i) return true;
        //为前i个会出现至少i头牛，表明出现了循环
      
    }

那么完整的check函数就是这个

bool check(int mid){
    int sum = 0;
    for(int i = 1 ; i <= mid ; i ++) b[i] = 0;
    for(int i = 1 ; i <= mid ; i ++){
        b[a[i]]++; 
    }
   
    for(int i = 1 ; i <= mid ; i ++){
        b[i] += b[i - 1];
        if(b[i] >= i) return true;;
    }
    return false;
}

ac代码就是


#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int b[N];
bool check(int mid){
    int sum = 0;
    for(int i = 1 ; i <= mid ; i ++) b[i] = 0;
    for(int i = 1 ; i <= mid ; i ++){
        b[a[i]]++; 
    }
   
    for(int i = 1 ; i <= mid ; i ++){
        b[i] += b[i - 1];
        if(b[i] >= i) return true;;
    }
    return false;
}
int main(){
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        int t;
        cin >> t;
        a[i] = n - t;
    }
    //cout << a[2] << "\n";
    int l = 1 , r = n;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;  
        //cout << l << " " << r << "\n"; 
    }
   cout << n - r;
}