A938. Lemonade Line--Silver
编程题
普及-
知识点
题目描述
It's a hot summer day out on the farm, and Farmer John is serving lemonade to
his $N$ cows! All $N$ cows (conveniently numbered $1 \dots N$) like lemonade,
but some of them like it more than others. In particular, cow $i$ is willing
to wait in a line behind at most $w_i$ cows to get her lemonade. Right now all
$N$ cows are in the fields, but as soon as Farmer John rings his cowbell, the
cows will immediately descend upon FJ's lemonade stand. They will all arrive
before he starts serving lemonade, but no two cows will arrive at the same
time. Furthermore, when cow $i$ arrives, she will join the line if and only if
there are at most $w_i$ cows already in line.
Farmer John wants to prepare some amount of lemonade in advance, but he does
not want to be wasteful. The number of cows who join the line might depend on
the order in which they arrive. Help him find the minimum possible number of
cows who join the line.
his $N$ cows! All $N$ cows (conveniently numbered $1 \dots N$) like lemonade,
but some of them like it more than others. In particular, cow $i$ is willing
to wait in a line behind at most $w_i$ cows to get her lemonade. Right now all
$N$ cows are in the fields, but as soon as Farmer John rings his cowbell, the
cows will immediately descend upon FJ's lemonade stand. They will all arrive
before he starts serving lemonade, but no two cows will arrive at the same
time. Furthermore, when cow $i$ arrives, she will join the line if and only if
there are at most $w_i$ cows already in line.
Farmer John wants to prepare some amount of lemonade in advance, but he does
not want to be wasteful. The number of cows who join the line might depend on
the order in which they arrive. Help him find the minimum possible number of
cows who join the line.
输入格式
The first line contains $N$, and the second line contains the $N$ space-
separated integers $w_1, w_2, \dots, w_N$. It is guaranteed that $1 \leq N
\leq 10^5$, and that $0 \leq w_i \leq 10^9$ for each cow $i$.
separated integers $w_1, w_2, \dots, w_N$. It is guaranteed that $1 \leq N
\leq 10^5$, and that $0 \leq w_i \leq 10^9$ for each cow $i$.
输出格式
Print the minimum possible number of cows who might join the line, among all
possible orders in which the cows might arrive.
possible orders in which the cows might arrive.
输入输出样例
输入 #1
5 7 1 400 2 2
输出 #1
3
说明/提示
In this setting, only three cows might end up in line (and this is the
smallest possible). Suppose the cows with $w = 7$ and $w = 400$ arrive first
and wait in line. Then the cow with $w = 1$ arrives and turns away, since 2
cows are already in line. The cows with $w = 2$ then arrive, one staying and
one turning away.
smallest possible). Suppose the cows with $w = 7$ and $w = 400$ arrive first
and wait in line. Then the cow with $w = 1$ arrives and turns away, since 2
cows are already in line. The cows with $w = 2$ then arrive, one staying and
one turning away.