これは Cow and Fields の解説で見たテクニックなのですが、他でも見たことがある気がするのでまとめておきます。
今回解きたいのは以下の問題。
長さ \(N\) の \(2\) 整数の組 \((A_i,B_i)\) があります。
このとき、相異なる \(2\) つを選んだ時の \(min(A_i+B_j,A_j+B_i)\) の最大値を求めてください。
\(2 \le N \le 10^5\)
\(|A_i,B_i| \le 10^{18} (1 \le i \le N)\)
まず、 \(A_i+B_j \le A_j+B_i\) となるときに \(A_i+B_j\) が min として採用されることを確認します。この式を変形すると
\(A_i-B_i \le A_j-B_j\) となります。
ということは、全要素を \(A_k-B_k\) の値の昇順にソートすると任意の \(i<j\) について \(A_i-B_i \le A_j-B_j\) が成立します。とすると、前にある要素から \(A_i\) を、後ろにある要素から \(B_j\) を採用することになります。
\(A\) について前から累積maxをとって \(\alpha\) 、 \(B\) について後ろから累積maxをとって \(\beta\) 、とすると、\(max( \alpha_k + \beta_{k+1} ) (1 \le k \le N-1)\) が解となります。
計算量は、ソートをボトルネックとした \(O(N \log N)\)です。
