小杨做题 题解

题目分析

小杨的做题计划是一个典型的递推过程：

• 第 1 天做 (a) 题，第 2 天做 (b) 题；
• 从第 3 天开始，每天做的题数等于前两天的题数之和；
• 一旦某一天做题数量达到或超过 (m)，则当天之后永远不再做题。

我们需要求出到第 (N) 天为止，小杨一共做了多少题。如果在中途已经达到了停止条件，那么实际做题天数会少于 (N) 天。

题目给出的数据范围很小：(a,b\le10)，(m<1,000,000)，(3\le N\le364)，因此直接模拟整个过程完全没有压力。需要注意的是，做题数量会随着天数增加而迅速增长（类似斐波那契数列），在累加过程中可能超出 int 的范围，所以要使用 long long 类型。

解题思路

我们可以用一个循环来模拟从第 3 天到第 (N) 天的做题情况。用两个变量分别记录前一天的做题数和前两天的做题数，不断更新。

具体步骤如下：

1. 读入 (a, b, m, N)。
2. 用变量 ans 记录总做题数，初始值为前两天的和：ans = a + b。
3. 从第 3 天开始，循环 i = 3 到 i = N：
   • 计算当天的做题数：c = a + b。
   • 将当天的做题数累加到 ans 中。
   • 判断 c 是否大于或等于 (m)：
     • 如果是，说明小杨从明天起不再做题，直接跳出循环。
     • 如果不是，则将 a 更新为 b，b 更新为 c，继续下一轮循环。
4. 循环结束后，输出 ans。

注意：循环是从第 3 天开始的，这是因为前两天的做题数已经直接累加到 ans 中了。即使第 3 天没有执行到（例如 (N=2) 的情况），题目保证 (N\ge3)，所以循环至少会执行一次。跳出循环后，后续的天数不会再做题，因此 ans 就是最终答案。

算法说明

本题采用的算法是模拟法，即直接按照题意模拟小杨每天的做题过程。由于数据范围很小，模拟到第 (N) 天（最多 364 天）完全可行。递推方程类似于斐波那契数列，但加入了一个停止条件：做题数量 (\ge m) 时立即停止。

时间复杂度分析

循环最多执行 (N-2) 次，而 (N\le364)，所以时间复杂度为 (O(N))，即常数级时间，完全可以在 1 秒内完成。空间复杂度为 (O(1))，只需要几个变量。

参考代码

下面的 C++ 代码严格按照上述思路实现，使用 long long 来避免数据溢出。

cpp
复制
1#include <cstdio>
2
3int main() {
4    long long a, b, m, n;
5    scanf("%lld%lld%lld%lld", &a, &b, &m, &n);
6
7    long long ans = a + b;  // 前两天的总做题数
8    long long c = 0;        // 当天做题数
9
10    for (long long i = 3; i <= n; ++i) {
11        c = a + b;          // 当天做题数 = 前两天的和
12        ans += c;           // 累加总题数
13        if (c >= m) {       // 达到停止条件
14            break;
15        }
16        a = b;              // 更新前两天的值
17        b = c;
18    }
19
20    printf("%lld\n", ans);
21    return 0;
22}

代码解释

• 第 5 行：使用 %lld 读入四个 long long 类型的变量。
• 第 7 行：ans 初始化为前两天的和，因为第 1 天和第 2 天是直接给出的。
• 第 10 行：从第 3 天开始循环，直到第 (n) 天。
• 第 11 行：计算当天的做题数 c。
• 第 12 行：将 c 加入总题数。
• 第 13 行：如果当天做题数已经达到或超过 (m)，则执行 break 跳出循环，之后不再累加。
• 第 16~17 行：如果还未达到停止条件，则将 b 变为新的“前一天”，a 变为新的“前两天”，为下一天做准备。
• 第 20 行：输出最终的总做题数。

这样，无论小杨是在第 (N) 天之前停止做题，还是做到了第 (N) 天，ans 中保留的都是正确的总题数。