QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

#21049. 柠檬水队伍

Statistics

炎热的夏日,Farmer John 要给 $N$ 头牛供应柠檬水!所有牛(编号 $1 \dots N$)都喜欢,不过喜爱程度各异。牛 $i$ 最多愿意排在 $w_i$ 头牛后面等待。现在她们都在田里,FJ 一摇铃就会立即涌向摊位。她们都会在开始供应前到达,且不会同时到达。牛 $i$ 到达时,当且仅当队伍中已有的牛至多 $w_i$ 头,才会加入队伍。

Farmer John 想提前准备适量柠檬水,避免浪费。排队牛的数量取决于到达顺序。求可能加入队伍的牛的最少数量。

输入格式

第一行包含 $N$,第二行包含 $N$ 个以空格分隔的整数 $w_1, w_2, \dots, w_N$。保证 $1 \leq N \leq 10^5$,且每头牛 $i$ 满足 $0 \leq w_i \leq 10^9$。

输出格式

输出所有可能到达顺序中加入队伍的牛的最少数量。

样例

输入格式 1

5
7 1 400 2 2

输出格式 1

3

说明

本例可能只有 $3$ 头排队,而且这是最少的。让 $w=7$ 和 $w=400$ 的牛先到并排队。随后 $w=1$ 的牛见已有 $2$ 头而离开。再让 $w=2$ 的牛到达,一头留下,一头离开。

题目作者:Dhruv Rohatgi

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.