题解

题目解析

• 输入输出：输入包含4行，分别为第1天做题数 $a$、第2天做题数 $b$、终止阈值 $m$、总天数 $N$；输出一个整数，表示 $N$ 天内小杨实际完成的总题数。
• 数据范围：$0 \leq a, b \leq 10$，$a, b < m \leq 10^6$，$3 \leq N \leq 364$。注意斐波那契式增长会很快超过 $m$，实际计算天数通常远小于 $N$。
• 复杂度要求：时间复杂度 $O(N)$，最多遍历 364 次；空间复杂度 $O(N)$（可优化至 $O(1)$），用于存储每日做题数或滚动计算。
• 算法知识点：递推、模拟、类斐波那契数列、条件终止

思路解析

1. 初始化：第 1 天和第 2 天的做题数直接由输入确定，分别为 $a$ 和 $b$，并将两者加入总和。
2. 递推规则：从第 3 天开始，若前一天（第 $i-1$ 天）的做题数小于 $m$，则第 $i$ 天做题数为前两日之和（$ans[i] = ans[i-1] + ans[i-2]$），并累加到总题数；否则立即终止循环（"接下来的所有日子里再也不做题"）。
3. 终止条件细节：判断依据是前一天是否已达阈值，确保第 $k$ 天做题数 $\geq m$ 时，第 $k$ 天的题量仍被计入，但从第 $k+1$ 天起停止累加。
4. 溢出防护：虽然题目保证 $m \leq 10^6$ 且触发终止后不再计算，但使用 long long 存储总和可避免极端情况下的溢出风险。

完整代码

#include <bits/stdc++.h>
using namespace std;

int ans[1000];  // 存储每天的做题数量，N<=364，数组大小充足

int main() {
    int a, b, m, n;
    cin >> a >> b >> m >> n;
    
    ans[1] = a;
    ans[2] = b;
    long long sum = a + b;  // 总题数，使用long long防止溢出
    
    // 从第3天开始递推
    for (int i = 3; i <= n; i++) {
        // 关键判断：只有前一天做题数<m，今天才继续做题
        if (ans[i - 1] < m) {
            ans[i] = ans[i - 1] + ans[i - 2];  // 类斐波那契递推
            sum += ans[i];
        }
        else {
            break;  // 前一天已达标，今天及以后不再做题
        }
    }
    
    cout << sum << endl;
    return 0;
}