下面是否有快速算法？

Question

我有两个排序数组A和B，每个长度为n。

我也有一组索引对S，索引在1到n之间。 （例如，如果n = 3，则S可以是（1,2），（2,3）和（1,1））。

我想要一个非常快速的算法（最好是O（log n）），使它找到来自S的最大化A [i] + B [j]的对（i，j）。

S上的任何预处理都可以完成（散列某些值等）。可以在A和B上完成任何O（n log n）预处理（因为无论如何都需要时间对它们进行排序），但是一旦预处理完成，后续具有各种预处理S的查询应该是快速的。

感谢您的任何想法。

Answer 1

这不能在小于O（n）的情况下完成。

如果S={(i,n-i+1)|1≤i≤n}你比对测试，因为i≠j S的每一个元素没有其他解决办法，既A[i]+B[n-i+1] < A[j]+B[n-j+1]和A[i]+B[n-i+1] ≥ A[j]+B[n-j+1]是可能的。