P4421 蜗牛与葡萄树（入门）

解题思路

蜗牛第一分钟爬6分米，之后每分钟都比上一分钟少爬1分米：第二分钟5分米、第三分钟4分米……树高20分米，问第几分钟爬到顶。这是一道"按规律累加"的模拟题，我们维护三个变量：h表示已经爬的高度，一开始是0；d表示这一分钟能爬多少分米，一开始是6；t表示已经过去的分钟数，一开始是0。while循环的条件是 h<20，也就是还没爬到顶就继续：每次循环先让 h+=d（加上这一分钟爬的高度），再 t++（时间过去1分钟），最后 d--（下一分钟少爬1分米，因为体力下降了）。这样循环会一直模拟到h刚好达到或超过20为止。边界情况：当爬完某一分钟正好等于20时（6+5+4+3+2=20），循环条件 h<20 变成假，循环结束，输出t=5；如果最后一次超过20（树再高一些），也一样会退出，因为我们要的是"到达或超过树顶"的时刻。

参考代码

// 程序用途：模拟蜗牛爬树，第一分钟爬6分米，之后每分钟少1分米，算爬到20分米树顶要几分钟
#include <iostream>
using namespace std;

int main() {
    int h = 0;                      // 已经爬的高度
    int d = 6;                      // 这一分钟爬的速度，第一分钟6分米
    int t = 0;                      // 已用的分钟数
    while (h < 20) {                // 还没爬到树顶就继续
        h += d;                     // 这一分钟爬上去的高度
        t++;                        // 分钟数加1
        d--;                        // 下一分钟少爬1分米
    }
    cout << t << endl;              // 输出爬到树顶需要的时间
    return 0;
}

复杂度分析

蜗牛每分钟爬的距离少1分米，最多爬几十分钟就停下来了。本题树高20分米，一共只循环5次，是固定次数，所以时间复杂度 O(1)；只用三个变量，额外空间复杂度 O(1)。