题目描述
小明喜欢去游乐场玩,他尤其喜欢旋转木马。每次乘坐旋转木马,都需要花费 8 元。每次去游乐场,可能会乘坐多次旋转木马。
妈妈每天会给小明 1 元零花钱。第 0 天时,小明没有零花钱。当小明手里的零花钱达到了 50 元,妈妈将不再给他零花钱。
妈妈计划带小明去游乐场 n 次,分别在第 a1,a2,⋯,an 天。一天可以去多次游乐场,因此 ai 可能相同。每次去游乐场,他会把手上的零花钱全部用来乘坐旋转木马,直到零花钱不足 8 元。
请问,小明去完 n 次游乐场后,他一共乘坐了几次旋转木马?
输入格式
第一行包含一个整数 n,表示计划去游乐场的次数。
第二行包含 n 个整数 a1,a2,⋯,an,表示小明去游乐场的日期。
数据保证 a1≤a2≤⋯≤an。
输出格式
输出一行一个整数,表示小明乘坐旋转木马的次数。
输入输出样例
输入 #1
5 1 17 70 75 79
输出 #1
9
说明/提示
样例解释
- 最开始时(第 0 天),小明手上没有钱。
- 第 1 天时,小明手上有 1 元。他去了游乐场,但钱不够乘坐旋转木马。
- 第 17 天时,小明手上有 17 元。他去游乐场可以玩 2 次旋转木马。还剩 1 元。
- 第 70 天时,小明手上有 50 元(其实到第 66 天,他就攒了 50 元,但接下来这几天,妈妈就不给他零花钱了)。他去游乐场可以玩 6 次旋转木马。还剩 2 元。
- 第 75 天时,小明手上有 7 元。他去了游乐场,但钱不够玩旋转木马。
- 第 79 天时,小明手上有 11 元。他去游乐场可以玩 1 次旋转木马。还剩 3 元。
他一共玩了 9 次旋转木马。
数据规模与约定
- 对于 100% 的测试数据,n≤10^5,ai≤10^9。
-
#include<bits/stdc++.h> using namespace std; int main() { int n,a[100010]={},s=0,y=0,x=1; bool f=1; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=a[n];) { if(f) { y++; y>50?y=50:y=y; } if(a[x]==i) { s+=y/8; y%=8; x++; if(a[x]==i) { f=0; continue; } } i++; f=1; } printf("%d",s); }