algorithm - 以下是否有快速算法？

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 进行任何预处理（散列某些值等）。

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

感谢您的任何想法。

Answer 1

这不能在小于 O(n) 的时间内完成。

如果S={(i,n-i+1)|1≤i≤n}除了测试 S 的每个元素之外没有其他解决方案，因为 for i≠j，两者A[i]+B[n-i+1] < A[j]+B[n-j+1]和A[i]+B[n-i+1] ≥ A[j]+B[n-j+1]都是可能的。