笔记——序列合并问题
作者:
wlyly
,
2021-08-01 14:51:27
,
所有人可见
,
阅读 283
1.
这是一种典型的问题,并不是什么算法。
大体框架是这样的:给出两个有序的序列,将它们合并后,求出合并后的序列的()?
()中可以填的东西有很多,如 中位数,第 $x$ 大的数……
2.
这种问题的解法大致分为三种:二分,双指针,贪心。
对于二分的类型,它必须满足所求值可以分开处理的性质,不然跟直接暴力合并排序没有区别。
对于双指针的类型,我们需要用两个指针,然后利用它们之间的关系来合并。
对于贪心的类型,题目所求的值很大可能是个最值,这时候我们就可以将它们的最值求起来,再求一次最值。
3.
例题:懒得翻太多,就找了一个Lick,然后这个是很典型的双指针做法。