算法复习（经典问题整理）_设a[1:n]是由不同实数组成的数组,如果 ia[j],则称实数对 (a[i], a

作者：Cpp五条 | 2024-06-14 04:55:06

踩

设a[1:n]是由不同实数组成的数组,如果 ia[j],则称实数对 (a[i], a[j])是

（分治，动态，贪心）经典问题整理

分治：

1、求两个有序数组的中位数和Topk问题
参考：https://www.cnblogs.com/voidsky/p/5373982.html
实际上述解法的渐进时间复杂度为O（logn），在第一个数组中不断二分查找c1的位置从而c2的位置也随之固定。

2、黑白点配对问题：给定平面上 n 个白点和 n 个黑点，试设计一个分治算法将每个白点与一个黑点相连，使得所有连线互不相交
参考：https://blog.csdn.net/u010244645/article/details/64920822
这个算法不是很稳定，他首先按照凸包算法，选定一个起始点，将剩余点按极角排序，用和起始点配对的第一个点将剩余解空间划分（划分时候必须保证两个解空间中的黑白点个数相同，才能保证算法的正确性），达到分治目的。

3、给定凸多边形 p1,p2,…,pn（边界逆时针顺序）和 n 个点 q1,q2,….,qn，试设计一个分治算法计算 q1,q2,….,qn中位于凸多边形 p1,p2,… ,pn内部的点的个数
这个算法的思路首先是wipeout，用矩形将一部分点筛除，然后选取凸包最左下方的点p0算极角（p，q都算），这样不在p0pi夹角内的q也被筛除

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】