题目解析
* 输入输出:输入包含4行,分别为第1天做题数 aaa、第2天做题数 bbb、终止阈值 mmm、总天数 NNN;输出一个整数,表示 NNN 天内小杨实际完成的总题数。
* 数据范围:0≤a,b≤100 \leq a, b \leq 100≤a,b≤10,a,b<m≤106a, b < m \leq 10^6a,b<m≤106,3≤N≤3643 \leq N \leq 3643≤N≤364。注意斐波那契式增长会很快超过 mmm,实际计算天数通常远小于 NNN。
* 复杂度要求:时间复杂度 O(N)O(N)O(N),最多遍历 364 次;空间复杂度 O(N)O(N)O(N)(可优化至 O(1)O(1)O(1)),用于存储每日做题数或滚动计算。
* 算法知识点:递推、模拟、类斐波那契数列、条件终止
思路解析
1. 初始化:第 1 天和第 2 天的做题数直接由输入确定,分别为 aaa 和 bbb,并将两者加入总和。
2. 递推规则:从第 3 天开始,若前一天(第 i−1i-1i−1 天)的做题数小于 mmm,则第 iii 天做题数为前两日之和(ans[i]=ans[i−1]+ans[i−2]ans[i] = ans[i-1] + ans[i-2]ans[i]=ans[i−1]+ans[i−2]),并累加到总题数;否则立即终止循环("接下来的所有日子里再也不做题")。
3. 终止条件细节:判断依据是前一天是否已达阈值,确保第 kkk 天做题数 ≥m\geq m≥m 时,第 kkk 天的题量仍被计入,但从第 k+1k+1k+1 天起停止累加。
4. 溢出防护:虽然题目保证 m≤106m \leq 10^6m≤106 且触发终止后不再计算,但使用 long long 存储总和可避免极端情况下的溢出风险。
完整代码