B3962 [语言月赛 202404] 游乐场 题解

· · 题解

Source & Knowledge

2024 年 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。

int current_money = 0; // 当前攒了多少钱
int x, y = 0; // 初始时为第 0 天

...

for (int i = 1; i <= n; i++) {
    cin >> x;
  current_money += (y - x); // 上一次到这一次一共攒了多少钱
  if (current_money > 50) current_money = 50; // 如果超过了 50 元，则不会有零花钱

  // 计算可以坐多少次旋转木马

  y = x; // 坐完旋转木马，这一天变为“上一次去游乐园在哪一天”
}

计算在有 current_money 元钱的情况下，可以坐多少次旋转木马。每 8 元可以坐一次旋转木马，因此坐旋转木马的次数是 current_money / 8（这里的 / 是 C++ 中的整除）。

int ans = 0; 

for ... {
    ...
    ans += current_money / 8;
    current_money -= (current_money / 8) * 8;
    ...
}

视频讲解