【题目来源】学而思编程冲刺信奥【题目描述】不知不觉已经进入炎热的夏天小猴发现暑假完了之后今年的CSP-J就临近比赛了所以小猴想提前做好复习规划小猴决定从下周一开始努力刷题备战CSP-J他计划周一至周五每天做a aa道题目周六和周日每天做b bb道题目。请你帮小猴计算按照计划他将在第几天实现做题数大于n nn题【输入】一行包含三个整数a aab bb和n nn。【输出】一行一个整数代表天数。【输入样例】10 20 99【输出样例】8【核心思想】问题分析给定周一至周五每天做a aa题、周六周日每天做b bb题的计划求累计做题数首次超过n nn题所需的天数。这是一个周期模拟问题核心在于利用周期性规律减少重复计算将大规模模拟优化为整周计算 剩余天数模拟。算法选择周期分解以7 77天为一个周期先计算完整周期的数量再模拟剩余不足一周的天数取模运算利用n m o d s n \bmod snmods提取不足一个周期的剩余量避免逐天遍历所有天数关键步骤计算周工作量s 5 × a 2 × b s 5 \times a 2 \times bs5×a2×b即一个完整周期7 77天的总做题量整周处理r e s ⌊ n / s ⌋ × 7 res \lfloor n / s \rfloor \times 7res⌊n/s⌋×7计算完整周期对应的天数n ← n m o d s n \leftarrow n \bmod sn←nmods得到剩余目标量模拟剩余天数定义周期内每日工作量数组d [ a , a , a , a , a , b , b ] d [a, a, a, a, a, b, b]d[a,a,a,a,a,b,b]逐天累加s u m sumsum直到s u m n sum nsumn总天数累加r e s ← r e s d a y res \leftarrow res dayres←resday其中d a y dayday为最后不足一周所需的天数输出结果r e s resres时间/空间复杂度时间复杂度O ( 1 ) O(1)O(1)整周计算为O ( 1 ) O(1)O(1)剩余天数模拟最多7 77天亦为O ( 1 ) O(1)O(1)空间复杂度O ( 1 ) O(1)O(1)仅需常数级别变量和固定长度为7 77的数组周期模拟的核心思想周期性规律利用当操作具有固定周期时不必逐天模拟而是通过除法快速跳过完整周期大幅降低时间复杂度取模提取余量n m o d s n \bmod snmods将大规模问题缩小为周期内的局部问题使得剩余部分可以在常数时间内完成模拟边界条件处理循环条件使用s u m ≤ n sum \leq nsum≤n确保累计量严格大于n nn时才停止满足题目大于n nn题的要求防溢出处理使用long long避免5 × a 2 × b 5 \times a 2 \times b5×a2×b在a , b a, ba,b较大时发生整数溢出适用于具有固定周期规律、需要计算累计量达到阈值所需步数的模拟类问题【解题思路】【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将 int 定义为 long long防止乘法溢出signedmain()// 使用 signed 替代 int因为 #define int long long{inta,b,n;// a: 周一至周五每天做题数, b: 周六周日每天做题数, n: 目标做题总数cinabn;// 读入三个整数ints5*a2*b;// s: 一周7天的总做题量 5天×a 2天×bintresn/s*7;// res: 完整周数对应的天数// n/s 得到完整周数乘以7得到完整周的天数intsum0;// sum: 当前周内累计做题数n%s;// n: 剩余不足一周的做题量// 一周每天的工作量数组周一到周五每天a题周六周日每天b题intd[]{a,a,a,a,a,b,b};intday0;// day: 当前周内经过的天数// 模拟不足一周的做题过程直到累计做题数超过剩余目标nwhile(sumn)// 当累计工作量小于等于剩余目标时继续{day;// 天数增加sumd[(day-1)%7];// 加上当天工作量用模7循环取一周中的某天}resday;// 总天数 完整周天数 最后不足一周的天数coutresendl;// 输出实现做题数大于n所需的总天数return0;}【运行结果】10 20 99 8
