Codeforces 1635F - Closest Pair
問題へのリンク
提出コード
解法
$ i < j < k
かつ
$ \max(w_i, w_j) \leq w_k
であるとする。
このとき
$ i, k
のペアが最適となることはありえない。
よって、各
$ i
について、左右それぞれについて自分より
$ w_i
が小さいもののうち最も近いものだけ考慮すればよい。
これによりペア数を
$ O(N)
に減らすことができた。