题解：学而思编程 猴子兄弟爬山

【题目来源】

学而思编程：猴子兄弟爬山

【题目描述】

已知皮皮和大智是关系非常友好的两只猴子，并且它们都居住在同一座山上。山高 \(h\) 米，皮皮在距离山脚 \(h_a\) 米的地方居住，大智在距离山脚 \(h_b\) 米的地方居住。

皮皮和大智相约爬山，它们约定从同一天的白天开始从自己居住的地方开始往山顶爬，每天皮皮和大智都会根据自己的实际情况决定自己的行为：

• 白天正常情况下，皮皮每天爬 \(u_a\) 米，大智每天爬 \(u_b\) 米，但是如果白天开始时对方比自己高，那么皮皮会多爬 \(add_a\) 米，大智会多爬 \(add_b\) 米。
• 黑夜正常情况下，皮皮每天掉 \(d_a\) 米，大智每天掉 \(d_b\) 米，但是如果黑夜开始时对方比自己高，那么皮皮会少掉 \(sub_a\) 米，大智会少掉 \(sub_b\) 米。

现在请你帮助计算皮皮和大智两只猴子都爬到山顶所需要的时间（天数），你需要回答 \(t\) 个这样的问题。数据数据保证两人一定能够在有限步数内登上山顶。

【输入】

第一行，包含一个正整数 \(t\)。

接下来 \(t\) 行，每行 \(11\) 个整数 \(h,h_a,h_b,u_a,u_b,add_a,add_b,d_a,d_b,sub_a,sub_b\)。

【输出】

共 \(t\) 行，每行一个整数，表示答案。

【输入样例】

2
8 1 3 3 2 1 1 2 1 1 1
30 2 20 14 2 3 1 2 1 1 0

【输出样例】

3
6

【核心思想】

1. 问题分析：给定山高 \(h\)，皮皮初始高度 \(h_a\)，大智初始高度 \(h_b\)。每天分白天和黑夜两个阶段：

   • 白天：各自爬 \(u_a\)/\(u_b\) 米；若对方比自己高，额外爬 \(add_a\)/\(add_b\) 米
   • 黑夜：各自掉 \(d_a\)/\(d_b\) 米；若对方比自己高，少掉 \(sub_a\)/\(sub_b\) 米

   求两只猴子都到达山顶（高度 \(\geq h\)）所需天数。这是一个模拟问题，直接按规则逐天模拟即可。

2. 算法选择：

   • 直接模拟：每天按白天 \(\to\) 黑夜的顺序更新两只猴子的高度，直到两者均 \(\geq h\)

3. 关键步骤：

   • 初始化：读取 \(t\)（测试组数），每组 \(11\) 个参数
   • 逐天模拟（当 \(h_a < h\) 或 \(h_b < h\) 时循环）：
     • 白天阶段：
       • 比较高度：若 \(h_a < h_b\)，皮皮额外爬 \(add_a\)；若 \(h_b < h_a\)，大智额外爬 \(add_b\)
       • 正常爬行：\(h_a += u_a\)，\(h_b += u_b\)
       • 登顶标记：若 \(h_a \geq h\)，设 \(h_a = 10^9\)（极大值，防止后续掉落影响）；同理 \(h_b\)
     • 黑夜阶段：
       • 比较高度：若 \(h_a < h_b\)，皮皮少掉 \(sub_a\)；若 \(h_b < h_a\)，大智少掉 \(sub_b\)
       • 正常掉落：\(h_a -= d_a\)，\(h_b -= d_b\)
     • 天数 \(cnt++\)
   • 输出答案 \(cnt\)

4. 时间/空间复杂度：

   • 时间复杂度：\(O(t \times D)\)，其中 \(D\) 为每组数据所需天数，数据保证有限步内登顶
   • 空间复杂度：\(O(1)\)，仅使用常数变量

5. 模拟的核心思想：

   • 分阶段处理：每天严格按"白天 \(\to\) 黑夜"顺序执行，白天先判断高低再爬行，黑夜先判断高低再掉落
   • 登顶保护：已登顶的猴子设为极大值，确保不再受掉落影响，且不会影响另一只猴子的比较判断（极大值始终大于对方）
   • 高低比较驱动：每天的关键决策（是否额外爬/少掉）完全由当天开始时的相对高度决定
   • 适用于规则明确的逐日/逐轮状态更新、双人博弈模拟类问题

【算法标签】

模拟

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int t;  // 测试数据组数int main()
{cin >> t;  // 输入测试数据组数while (t--)  // 处理每组测试数据{int h, ha, hb, ua, ub, adda, addb, da, db, suba, subb;  // 变量声明cin >> h >> ha >> hb >> ua >> ub >> adda >> addb >> da >> db >> suba >> subb;  // 输入初始参数int cnt = 0;  // 计数器，记录操作次数while (ha<h || hb<h)  // 循环直到两个数都大于等于h{cnt++;  // 操作次数加1if (ha<hb)  // 如果ha小于hbha += adda;  // ha加上addaelse if (hb<ha)  // 如果hb小于hahb += addb;  // hb加上addbha += ua;  // ha加上uahb += ub;  // hb加上ubif (ha>=h)  // 如果ha大于等于hha = 1e9;  // 将ha设为极大值if (hb>=h)  // 如果hb大于等于hhb = 1e9;  // 将hb设为极大值if (ha<hb)  // 如果ha小于hbha += suba;  // ha加上subaelse if (hb<ha)  // 如果hb小于hahb += subb;  // hb加上subbha -= da;  // ha减去dahb -= db;  // hb减去db}cout << cnt << endl;  // 输出操作次数}return 0;
}

【运行结果】

2
8 1 3 3 2 1 1 2 1 1 1
3
30 2 20 14 2 3 1 2 1 1 0
6