どう見ても貪欲にしか見えないけど、どう貪欲にとってもWAする恐ろしい問題でした。
と思いきや、実は正当な解法も貪欲法を使うという。

解法

問題文の感じから、二分探索できそうだとアタリがつけられる。
二分探索ができるとすれば、判定問題は「 $K$ 組の鏡餅を作れるか否か？」になる。

この判定問題は小さい餅 $K$ 個を小さい方から見て、残りの $N - K$ 個の餅の小さい方から貪欲にマッチさせることが可能かチェックすることで解ける。

判定問題の解法の正当性を確認する。

まず、 $K$ 組の鏡餅を作ることのできるマッチングがあるとする。このうち上に乗る餅と下に乗る餅の大小関係が異なる2組を取り出す。具体的には、上に乗る餅が $X _ {1}, X _ {2}$ 、下敷きになる餅が $Y _ {1}, Y _ {2}$ であるとして、 $X _ {1} \lt X _ {2}$ かつ $Y _ {1} \gt Y _ {2}$ であるような2つの組 $(X _ {1}, Y _ {1}), (X _ {2}, Y _ {2})$ を取り出す。
このとき、 $2X _ {1} \lt 2X _ {2} \lt Y _ {2} \lt Y _ {1}$ であるため、 $X _ {2}$ は $Y _ {1}$ ともマッチ可能であり、 $X _ {1}$ と $Y _ {2}$ もマッチ可能であることもわかる。
したがって、 $(X _ {1}, Y _ {2}), (X _ {2}, Y _ {1})$ も正当なマッチングであり、正当なマッチング $(X _ {1}, Y _ {1}), (X _ {2}, Y _ {2}), ... , (X _ {K}, Y _ {K})$ に対してこのような2つ組が存在する限り入れ替えを繰り返すことで、 $X _ {1} \le X _ {2} \le ... \le X _ {K}$ かつ $Y _ {1} \le Y _ {2} \le ... \le Y _ {K}$ とすることができる。
以上より、正当なマッチングが存在する場合、上に乗る餅、下敷きになる餅を小さい方から貪欲にマッチングすることで構築が可能なことがわかった。