目前我们有两个序列 \(a\) 与 \(b\),分别从两个序列里面取出来一个值相乘,要求 \(ab\) 的值最大/最小,此时该怎么办(\(a,b\) 可为负)。
这个题其实很简单,但是遇到的时候总归要想一下,为了让自己安心点,就整理一下把。
我们从数和量的角度去思考,设 \(b\) 为我们选择的数(值),而 \(a\) 是量。对于一个固定的值 \(b\) 来说的话,如果 \(ab\) 的值是最值,那么 \(a\) 一定也是最值,因为只有量足够大或者少,得到的结果的量才会尽量多或者少。同理,对于一个固定的 \(a\) 来说,只有量足够大/或者小, \(ab\) 才能尽量大/小。因此 \(ab\) 的最值一定是由 \(a\) 和 \(b\) 分别的最值组成的,即:
这是对于求两个序列乘积的最值。那么如果是求靠近某个值的的数值呢。
本质上,求最值也就是求靠近 \(+\infty\) 或者 \(-\infty\) 的数值。如果这个 \(\infty\) 变成一个常数 \(k\)。此时我们应该怎么求呢?
假设我们有 \(ab =k\),那么也就是有 \(a = \frac kb\),因此对于一个数 \(b\),我们可以直接二分 \(a = \frac kb\)。那么对于每个 \(b\) 他们都可以找出来一个乘积结果靠近 \(k\) 的 \(a\)(因为 \(\frac k b\) 大概率是分数,所以二分的数值不一定存在,但是可以通过再处理,搞出最靠近的 \(a\),详见不存在的二分)。那么最靠近 \(k\) 的 \(ab\) 乘积也就一定在这里面,求差值的绝对值最小即可。
这时候我们再回来看看求最值,可以发现,求最值本质上就是这个 \(k\) 是无穷大/无穷小。而用最值求出最值不过是特殊情况而已,因为当 \(k\) 趋于无穷时,只有最值有优势 “达到” \(k\),而对于 \(k\) 比较小的情况,这种优势就不明显了,从而很难利用性质,这两种做法的时间复杂度也就有巨大的差异。
这时候又可以联想序列变换,很多时候,对于序列的处理也就是先变换,再处理。嘶,我在说什么。
