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）
第二行，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轮扫雷中购买地雷探测器。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版