USACO备考冲刺必刷题 | P4379 Lemonade Line

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

这是农场上一个炎热的夏日，Farmer John要给他的N头奶牛发柠檬汽水了！所有的N头奶牛（方便起见，编号1…N）都喜欢柠檬汽水，只是有些喜欢的程度更高一些。具体地说，奶牛i为了获得柠檬汽水最多愿意排在wi头奶牛之后。现在所有的N头奶牛都在田里，但是只要Farmer John敲响牛铃，这些奶牛就会立刻赶到FJ的柠檬汽水站。她们会在FJ开始分发柠檬汽水之前到达，但是没有两头奶牛会在同一时刻到达。此外，当奶牛i到达时，当且仅当至多有wi头奶牛在排队时她会来排队。

Farmer John想要提前准备一定量的柠檬汽水，但是他不想浪费。排队的奶牛的数量可能取决于她们到达的顺序。帮助他求出最少可能的排队的奶牛数量。

【输入】

第一行包含N，第二行包含N个用空格分隔的整数w1,w2,…,wN。输入保证1≤N≤10^5，此外对于每头奶牛i，0≤wi≤10^9。

【输出】

输出在所有可能的奶牛到达顺序之下，最小可能的排队的奶牛数量。

【输入样例】

5
7 1 400 2 2

【输出样例】

3

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, w[100005], ans=0;
bool cmp(int x, int y)
{
    return x>y;
}
int main()
{
    cin >> n;  // 输入n
    for (int i=1; i<=n; i++) {  // 输入n头奶牛的wi
        cin >> w[i];
    }
    sort(w+1, w+n+1, cmp);  // 按照从大到小方式排序
    for (int i=1; i<=n; i++) {  // 遍历n头奶牛
        if (w[i]>=i-1) ans++;  // 如果wi大于等于i-1，即大于等于队伍中的奶牛数，则说明这头奶牛可以进入队伍中
        else break;  // 否则结束循环（后面都肯定进不了队伍了）
    }
    cout << ans << endl;  // 输出结果
    return 0;
}

【运行结果】

5
7 1 400 2 2
3