刷题
刷题
learn
learn
日期
Aug 30, 2024
- 思考一个问题在大范围上的答案，是否等于，左部分的答案+右部分的答案+跨越左右产生的答案
- 计算“跨越左右产生的答案”时，如果加上左、右各自有序这个设定，会不会获得计算的便利性
- 如果以上两点都成立，那么该问题很可能被归并分治解决（当然不完全一定）
- 求解答案的过程中只需要加入归并排序的过程即可，因为要让左、右各自有序，来获得计算的便利性
补充：
- 一些用归并分治解决的问题，往往也可以用线段树、树状数组等解法。时间复杂度也都是最优解
- 归并分治不仅可以解决简单问题，还可以解决很多较难的问题，只要符合上面的特征。比如二维空间里任何两点间距离的最短距离问题
- 还有一个常考的算法：整块分治
刷题 (1)
名称
日期
复选框