P6932: 柠檬汽水
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
这是农场上一个炎热的夏日，Farmer John
要给他的N
头奶牛发柠檬汽水了！所有的N
头奶牛（方便起见，编号为1…N
）都喜欢柠檬汽水，只是有些喜欢的程度更高一些。具体地说，奶牛i
为了获得柠檬汽水最多愿意排在wi
头奶牛之后。现在所有的N
头奶牛都在田里，但是只要Farmer John
敲响牛铃，这些奶牛就会立刻赶到FJ的柠檬汽水站。她们会在FJ开始分发柠檬汽水之前到达，但是没有两头奶牛会在同一时刻到达。此外，当奶牛i到达时，当且仅当至多有wi
头奶牛在排队时她会来排队。
Farmer John
想要提前准备一定量的柠檬汽水，但是他不想浪费。排队的奶牛的数量可能取决于她们到达的顺序。帮助他求出最少可能的排队的奶牛数量。
【
输入格式】
（lemonade.in
）：
第一行包含N
，第二行包含N
个用空格分隔的整数w1,w2,…,wN
。输入保证1≤N≤10
^5
，此外对于每头奶牛i
，0≤wi≤10
^9
。
【
输出格式】
（lemonade.out
）：
输出在所有可能的奶牛到达顺序之下，最小可能的排队的奶牛数量。
【
输入样例】
：
5
7 1 400 2 2
【
输出样例】
：
3
【样例说明】
在这个情况下，可能最后仅有三头奶牛在队伍中（这也是最小可能值）。假设w=7
和w=400
的奶牛先到并等在队伍中。然后w=1
的奶牛到达并且会离开，这是由于已经有2
头奶牛在队伍中了。然后w=2的两头奶牛到达，一头留下排队，一头离开。