Maxmilite
2024-04-24 08:38:08
Solution## Source & Knowledge2024 年 4 月语言月赛，由洛谷网校入门计划/基础计划提供。## 题目大意妈妈每天会给小明 $1$ 元零花钱。第 $0$ 天时，小明没有零花钱。当小明手里的零花钱达到了 $50$ 元，妈妈将不再给他零花钱。妈妈计划带小明去游乐场 $n$ 次，分别在第 $a_1,a_2,\cdots,a_n$ 天。在游乐场可以乘坐旋转木马，**每次**乘坐旋转木马都需要花费 $8$ 元。每次去游乐场，会把手上的零花钱全部用来乘坐旋转木马，直到零花钱不足 $8$ 元。求最终乘坐旋转木马的总次数。## 题目分析一个比较容易想到的思路是，使用一个 `for` 循环按天枚举，每天获得 $1$ 元零花钱，同时检查该天是否可以去游乐园。但是 $a_i \leq 10^9$，直接枚举天数会超时。注意到，比较重要的是去游乐园的那些天，其他天只是在攒钱。又 $n \leq 10^5$，因此可以将枚举天数转化为枚举去游乐园的那些天数。由于 $a_1 \leq a_2 \leq \cdots \leq a_n$，因此可以建立两个变量 $x, y$，分别代表当前是哪一天和上一次去游乐园在哪一天。之后使用 `for` 循环，每次读入 $x$，计算**从上一次 $y$ 到这一次 $x$** 一共攒了多少钱，之后将 $y$ 改为 $x$。```cppint current_money = 0; // 当前攒了多少钱int x, y = 0; // 初始时为第 0 天... for (int i = 1; i > x; current_money += (y - x); // 上一次到这一次一共攒了多少钱 if (current_money > 50) current_money = 50; // 如果超过了 50 元，则不会有零花钱// 计算可以坐多少次旋转木马y = x; // 坐完旋转木马，这一天变为“上一次去游乐园在哪一天”}```计算在有 `current_money` 元钱的情况下，可以坐多少次旋转木马。每 $8$ 元可以坐一次旋转木马，因此坐旋转木马的次数是 `current_money / 8`（这里的 `/` 是 C++ 中的整除）。```cppint ans = 0; for ... {...ans += current_money / 8;current_money -= (current_money / 8) * 8;...}```## 视频讲解