Lemonade Line 题解

题面:

翻译:

在一个夏天,农夫给奶牛们提供一些柠檬汁.
奶牛们许哟啊排队领取.
每头奶牛的耐心不同,用wi来表示,当一头奶牛到达时,如果队伍的长度不大于wi,那么奶牛就会选择排队,否则就会掉头离去
奶牛的到来是由顺序的,
所以最终会有多少头奶牛领取到柠檬汁

输入:

第一行是一个数字n,代表奶牛的数量
第二行是n个数字,代表奶牛的耐心.
输入的顺序代表奶牛到达的顺序.

输出:

一个数字,拿到柠檬汁的奶牛的数量.

题目分析:

是一道水题,可以直接模拟.
我们用一个变量waiting来存储正在等待的奶牛的数量.
然后开始模拟排队
一开始waiting为0.
对于每一头奶牛i^th,如果他到达时,waiting的数值不大于wi,那么他就会开始排队,所以waiting+1.
否则就掉头离去,开始 处理下一头奶牛.

最后得到的队列中等待的奶牛数量waiting就是最终拿到柠檬汁的奶牛的数量.

代码:

#include<bits/stdc++.h>

long n, w[100000], waiting;

bool cmp(long a, long b){
    return a > b;
}

int main(){
    scanf("%ld", &n);
    for(long i = 0; i < n; ++i) scanf("%ld", w+i);

    std::sort(w, w+n, cmp);

    long i = 0;
    while(i < n){
        if(waiting <= w[i]){
            waiting++;
        }
        i++;
    }
    printf("%ld\n", waiting);
}