Responsive image

问题 3182 --扫雷

3182: 扫雷

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 35
[提交][状态][讨论版][命题人:]

题目描述

小劉喜欢玩扫雷，但是他玩的扫雷游戏有名为“地雷探测器”的特殊道具。 具体来说，小劉会进行n轮扫雷。每轮扫雷开始之前，小劉会获得1枚扫雷币。扫雷币在每轮扫 雷结束后不会回收，可以保留至下一轮扫雷。小劉知道，在第i轮（1≤i≤n）扫雷中，花费 ci 枚扫 雷币可以购买一个地雷探测器，清除地图中的一个雷。地雷探测器在一轮扫雷中可以购买任意次。 现在小劉想知道，在这n轮扫雷中最多能购买多少个地雷探测器呢？

输入描述

第一行，一个正整数n（1≤n≤2×1e5），表示扫雷轮数。 
第二行，n个正整数c1,c2,...,cn（1≤ci ≤1e9）

输出描述

一行，一个非负整数，表示答案。

样例输入

6
3 2 5 3 4 3

样例输出

2

提示

第二个样例输入：

5

6 3 3 4 2

输出：

2

第三个样例输入：

5 

7 6 5 9 8

输出：

0





对于第一个样例，小劉 可以选择在第2轮与第6轮扫雷中各购买一个地雷探测器。具体过程如下： 

• 获得1枚扫雷币，目前有1枚扫雷币。第1轮扫雷开始，不购买地雷探测器。

 • 获得1枚扫雷币，目前有2枚扫雷币。第2轮扫雷开始，购买一个地雷探测器，目前有0枚扫雷币。

 • 获得1枚扫雷币，目前有1枚扫雷币。第3轮扫雷开始，不购买地雷探测器。 

• 获得1枚扫雷币，目前有2枚扫雷币。第4轮扫雷开始，不购买地雷探测器。

 • 获得1枚扫雷币，目前有3枚扫雷币。第5轮扫雷开始，不购买地雷探测器。

 • 获得1枚扫雷币，目前有4枚扫雷币。第6轮扫雷开始，购买一个地雷探测器，目前有1枚扫雷币。

 对于第二个样例，小劉 可以选择在第5轮扫雷中购买两个地雷探测器。

 对于第三个样例，小劉 无法在这5轮扫雷中购买地雷探测器。

来源

23软3刘震峰 

[提交][状态]
ACM算法攻关部