自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:16:13，当前版本为作者最后更新于2024-04-24 08:38:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
    ...
}

视频讲解