皆様ありがとうございます．なんとか理解できたつもりです．

1. 累積させた配列を作成してソートする．
2. その配列を左から順に見ていき(a[i], 1 ≦ i ≦ n)，右の残りの配列の中でa[i] との差が最も x に近い値を求める．
2.1 その際に二分探索で求める．

ということでしょうか．

これなら，確かに n * log n です．

これは思いつきません．ソートと二分探索が効いてますね．
二分探索は探索して見付からなかったときに最終位置と
左右どちらかで近い方を選択することでできるのかな．．

>>234
累積配列の最初に，0 があるおかげで，a[2] 〜 a[n] じゃなくて a[1] 〜 a[n]
の部分列が求められるのか．こういうの苦手です．

>>245
便利な関数がいっぱいあるのだと勉強になりました．
partial_sum とかそのまんまのがあるんですね．
find_nearest がむずい…(´･ω･ :;.. 頑張ります．

感心してばかりでした．ありがとうございました．