语法快速入门

循环结构

sy875: 逃离魔法塔底简单

implementaiton, https://sunnywhy.com/sfbj/2/4/875

在一个遥远的王国里，有一位小精灵被困在一座深不可测的魔法塔底部。为了逃脱，小精灵每次都会飞升英尺，但由于法力有限，每次飞升后她都需要恢复魔力。在恢复魔力的过程中，小精灵会因为魔法塔的反作用力下降英尺。之后，她会重复飞升和恢复魔力的过程。小精灵要飞出塔顶，至少需要多少次飞升？如果她最后一次飞升后刚好达到塔顶，也视为她已经成功逃脱。

输入描述

输入一行包含三个整数 n 、u、d（1 <= n <= 1000, 1 <= u <= 100, 1 <= d <= 1000），分别表示魔法塔的高度，小精灵每次飞升的高度，以及每次下降的高度。

数据保证小精灵能逃脱。

输出描述

输出一个整数，表示小精灵飞出塔顶所需的最少飞升次数。

样例1

输入

20 5 2

输出

解释

塔的高度为英尺，小精灵每次飞升英尺，但会下降英尺。具体过程如下：

第一次飞升后，小精灵位于英尺（高度）。
恢复魔力后，小精灵下降到英尺（高度）。
第二次飞升后，小精灵位于英尺（高度）。
恢复魔力后，小精灵下降到英尺（高度）。
第三次飞升后，小精灵位于英尺（高度）。
恢复魔力后，小精灵下降到英尺（高度）。
第四次飞升后，小精灵位于英尺（高度）。
恢复魔力后，小精灵下降到英尺（高度）。
第五次飞升后，小精灵位于英尺（高度）。
恢复魔力后，小精灵下降到英尺（高度）。
第六次飞升后，小精灵位于英尺（高度），刚好到达塔顶，逃脱成功。

因此，小精灵需要进行次飞升才能成功逃脱。

这道题是一个经典的“蜗牛爬井”问题的变体。题目核心在于：最后一次飞升如果触及或超过了塔顶，小精灵就直接逃脱了，不再会发生下降。

由于题目给出的数据范围较大（ $H, U, D \leq 10^{9}$ ），直接使用循环（while）模拟每一天的过程在极端情况下可能会超时（例如每次只净上升 1 英尺，需要循环 $10^{9}$ 次）。但在“入门”难度下，我们先掌握模拟法，再理解数学法。

方法一：模拟法（使用 while 循环）

这是最直观的解法，适合理解题目逻辑。

cpp

#include <iostream>
using namespace std;

int main() {
    // 使用 long long 防止大数运算溢出
    long long H, U, D;
    cin >> H >> U >> D;

    long long current_h = 0; // 当前高度
    int count = 0;           // 飞升次数

    while (true) {
        count++;             // 开始一次飞升
        current_h += U;      // 向上飞行 U 英尺

        // 关键判断：如果飞升后高度达到或超过塔顶，直接成功，跳出循环
        if (current_h >= H) {
            break;
        }

        // 如果没到顶，休息并下降 D 英尺
        current_h -= D;
    }

    cout << count << endl;
    return 0;
}

方法二：数学公式法（ $O (1)$ 时间复杂度）

如果 $H$ 很大且 $U$ 与 $D$ 非常接近，上面的循环会运行很久。为了追求更高效率，我们可以用数学推导：

最后一次飞升：小精灵最后一次飞升必然能走 $U$ 英尺。这意味着在此之前，她只需要爬到 $H - U$ 的高度即可。
净上升高度：每一次“飞升+下降”的周期内，小精灵实际净上升的高度是 $U - D$ 。
计算周期：
- 需要通过完整周期完成的高度是 $H - U$ 。
- 所需完整周期数 $k = ⌈ \frac{H - U}{U - D} ⌉$ （向上取整）。
总次数：总飞升次数 = $k$ 次完整周期 + 最后那 1 次飞升。

公式实现：

cpp

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long H, U, D;
    cin >> H >> U >> D;

    if (H <= U) {
        // 如果第一次飞升就能到顶
        cout << 1 << endl;
    } else {
        // 需要飞升的净距离
        long long remaining = H - U;
        long long net_up = U - D;
        
        // 计算需要多少个完整的“升+降”周期（向上取整）
        // (a + b - 1) / b 是整数除法中实现向上取整的技巧
        long long cycles = (remaining + net_up - 1) / net_up;
        
        // 结果 = 周期数 + 最后一次飞升
        cout << cycles + 1 << endl;
    }

    return 0;
}

关键点总结

顺序很重要：必须先加 $U$ ，立即判断是否过线，然后再减 $D$ 。如果先减再判断，结果就会出错。
数据类型：虽然 $10^{9}$ 在 int 范围内，但如果计算过程中涉及加法或复杂的数学公式，建议统一使用 long long 以防万一。

语法快速入门 ​

循环结构 ​

sy875: 逃离魔法塔底 简单 ​

方法一：模拟法（使用 while 循环） ​