#PU835. USACO 2018 US Open Contest, Silver — Problem 2. Lemonade Line

    ID: 1593 传统题 文件IO:lemonade 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:open18来源:usaco.orgscoring:equal_test_cases线段树排序

USACO 2018 US Open Contest, Silver — Problem 2. Lemonade Line

USACO 2018 US Open Contest, Silver — Problem 2. Lemonade Line

题目描述

It's a hot summer day out on the farm, and Farmer John is serving lemonade to his NN cows! All NN cows (conveniently numbered 1…N1 \dots N) like lemonade, but some of them like it more than others. In particular, cow ii is willing to wait in a line behind at most wiw_i cows to get her lemonade. Right now all NN 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 ii arrives, she will join the line if and only if there are at most wiw_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 NN, and the second line contains the NN space-separated integers w1,w2,…,wNw_1, w_2, \dots, w_N. It is guaranteed that 1≤N≤1051 \leq N \leq 10^5, and that 0≤wi≤1090 \leq w_i \leq 10^9 for each cow ii.

输出格式

Print the minimum possible number of cows who might join the line, among all possible orders in which the cows might arrive.

数据范围

(见题面原文)

样例

样例 1

5
7 1 400 2 2
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.
Problem credits: Dhruv Rohatgi