下面是否有快速算法？

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]是可能的。