Lemonade Line

题目描述

这是农场里炎热的夏日，农夫约翰正在给他的 $N$ 头奶牛供应柠檬水！所有的 $N$ 头奶牛（方便起见编号为 $1 \dots N$）都喜欢柠檬水，但其中一些比另一些更喜欢。具体来说，奶牛 $i$ 愿意在队伍中最多排在 $w_i$ 头奶牛后面来获得她的柠檬水。 现在所有 $N$ 头奶牛都在田里，但一旦农夫约翰摇响牛铃，奶牛们会立刻涌向 FJ 的柠檬水摊位。它们都会在他开始供应柠檬水之前到达，但不会有两头奶牛同时到达。 此外，当奶牛 $i$ 到达时，当且仅当队伍里已经有不超过 $w_i$ 头奶牛时，她才会加入队伍。 农夫约翰想提前准备一定量的柠檬水，但他不想浪费。加入队伍的奶牛数量可能取决于它们到达的顺序。请帮助他找出可能加入队伍的奶牛数量的最小值。

输入格式

第一行包含 $N$，第二行包含 $N$ 个用空格分隔的整数 $w_1, w_2, \dots, w_N$。保证 $1 \leq N \leq 10^5$，并且对每头奶牛 $i$ 都有 $0 \leq w_i \leq 10^9$。

输出格式

在所有可能的到达顺序中，输出可能加入队伍的奶牛数量的最小值。

5
7 1 400 2 2

3

提示

在这种情况下，最终队伍里可能只有三头奶牛（并且这是最小可能值）。假设 $w = 7$ 和 $w = 400$ 的奶牛先到并在队伍里等待。然后 $w = 1$ 的奶牛到达并离开，因为此时队伍里已经有 2 头奶牛。接着 $w = 2$ 的奶牛到达，其中一头留下，另一头离开。 题目来源：Dhruv Rohatgi

标签: USACO|2018|Silver

来源

USACO|2018|Silver