3044. [USACO Open18 Silver]Lemonade Line

【题目描述】

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

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

【输入格式】

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

【输出格式】

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

【样例输入】

5
7 1 400 2 2

【样例输出】

3

【数据规模】

$40$%的数据$N<=500$;
$100$%的数据$N<=10000$;

【提示】

在这个情况下，可能最后仅有三头奶牛在队伍中（这也是最小可能值）。假设$w=7$和$w=400$的奶牛先到并等在队伍中。然后$w=1$的奶牛到达并且会离开，这是由于已经有$2$头奶在队伍中了。然后$w=2$的两头奶牛到达，一头留下排队，一头离开。

【来源】

USACO 2018 OPEN CONTEST Silver Problem 2

供题：Dhruv Rohatgi