题目名称 3044. [USACO Open18Silver]Lemonade Line
输入输出 lemonade_silver_18open.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 程远洋 2018-11-03
开放分组 全部用户
提交状态
分类标签
通过:11, 提交:23, 通过率:47.83%
Gravatar雾茗 100 0.000 s C++
GravatarShallowDream雨梨 100 0.000 s C++
Gravatarleon 100 0.001 s C++
GravatarBenjamin 100 0.010 s C++
Gravatar梦那边的美好ETMN 100 0.014 s C++
Gravatar数声风笛离亭晚 100 0.014 s C++
Gravatarwither 100 0.015 s C++
Gravatar神秘 100 0.016 s C++
Gravatar@@@ 100 0.017 s C++
Gravatar瑆の時間~無盡輪迴·林蔭 100 0.027 s C++
关于 Lemonade Line 的讨论

3044. [USACO Open18Silver]Lemonade Line

★   输入文件:lemonade_silver_18open.in   输出文件:lemonade_silver_18open.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】


这是农场上一个炎热的夏日,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

【数据规模】

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

【提示】


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


【来源】

USACO 2018 OPEN CONTEST Silver Problem 2

供题:Dhruv Rohatgi