解题思路
抽象输入
以前经常开玩笑给py写上cin cout, 没想到, 这次真得手写cin了…
乍一看, 这题不就是差分吗? 有什么难的? 上手写了啊, 写完一交, MLE! 不对, 肯定是读入存数组里炸了, 再试试, 改了改哈, 一交, MLE! 那肯定是读入字符串太多了, 上stdin, 又改了哈, 这次厉害, 一个个读入, 读完还del, 绝对不可能爆空间了, 一交, TLE!
点解呢? 全部读进来不行, 一个个读也不行, 那就折中, 一块块来.chunk = sys.stdin.read(8192)
而后一点点把数字提取出来. 即可正常解题.
输入部分代码:
1 | from collections.abc import Generator |
真正的题解
频繁的区域变动当然是用差分啦, 不知道差分也没关系, 差分是一种非常高效的处理区间更新的方法, 假设老师在黑板上记录学生每天的课堂表现得分:
- 周一: $10$分
- 周二: $15$分
- 周三: $12$分
- 周四: $18$分
差分就是每天得分的变化量:
- 周一到周二: $+5$分 ($15 - 10 = 5$)
- 周二到周三: $-3$分 ($12 - 15 = -3$)
- 周三到周四: $+6$分 ($18 - 12 = 6$)
这些变化量就是差分, 它反映了学生每天得分的增减情况. 只要知道了初值, 就可以很轻松的通过差分数组得出每个节点的数值情况.
回到本题, 我们只需要在差分数组$x-1$处标记$+z$, 在$y$处标记$-z$即可快速登记分数变动.
再耗费$O(n)$的时间还原出答案数组,求最小值即可. 总时间复杂度为$O(n+p)$
代码
1 | inp = chunk_reader() # 上文有提到 |
- 本文链接: https://www.zh314.xyz/2025/01/24/洛谷-P2367-语文成绩-Python题解/
- 版权声明: 本博客所有文章除特别声明外,均默认采用 CC BY-NC-SA 4.0 许可协议。