問題

考え方

きれいな問題で好き。 $\{A_N\}$ はソートしても問題がないのでソートする。マッチングする際に $A_i$ が大きい値ほど候補になる相手が厳しく、候補が絞られるので $A_i$ が大きい値から考えていく。

サンプル1 の場合ソート後の数列で考えると以下のようになっていて

4 6
1 2 3 4

$a_3(0-indexed)$ の候補になれる数は $a_1=2$ までである。

$i$ 番目について考える時、候補の相手は二分探索で求めることができる。 $[0, i-1]$ の範囲に対して $K-a_i$ 以下の最大の要素のindex $j$ を求めれば良い。 $N$ は偶数なので、 $\displaystyle \frac{N}{2}$ ペアを作れば良い。二分探索する回数は $\displaystyle \frac{N}{2}$ である。また後ろから考えて、すでに $cnt$ 人ペアを作っている時で $i$ 番目について考える時、その候補に含まれる数のうち、 $cnt$ 人はすでにペアになっているので候補の対象にはなりえない。よって、 $cnt$ 分は候補の数から差し引く。