#AT0016. [USACO18OPEN] Lemonade Line S

    ID: 467 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>算法基础贪心排序2018USACO快速排序

[USACO18OPEN] Lemonade Line S

题目描述

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

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

输入格式

第一行包含NN,第二行包含NN个用空格分隔的整数w1,w2,,wNw_1, w_2, \dots, w_N。输入保证1N1051 \leq N \leq 10^5,此外对于每头奶牛ii0wi1090 \leq w_i \leq 10^9

输出格式

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

5
7 1 400 2 2
3

提示

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

供题:Dhruv Rohatgi