問題

https://atcoder.jp/contests/abc388/tasks/abc388_e

解法

最小からマッチングするように貪欲しても最大からマッチングするように貪欲するのも、どちらも嘘解法になる。

例

6
1 1 2 3 4 6

実際の答え

2-6 ,1-4 ,1-3

最小からマッチング

1-2 ,1-3

最大からのマッチング

6-3,4-2

ここで一番多く作れる可能性について考える。便宜上 $L,R$ を以下のように定義する。( $A$ を前半分と後ろ半分に分けただけ)

$$ L = {A_1,A_2, \dots \,,A_{N/2}} \\ R = {A_{N/2+1},A_{N/2+2}, \dots,A_{N}} $$

一番多く鏡餅を作れる場合 $K =\frac{N}{2}$ となる。この場合 $L_1$ と $R_1$ , $L_2$ と $R_2$ $\dots, \,L_{N/2}$ と $R_{N/2}$ がマッチングして餅を作ることになる。一番多く作れる場合でも小さいほうの餅は $L$ からしか取らないことがわかる。つまり $K \lt \frac{N}{2}$ の状況でも小さい方の餅は $L$ からしか取らない。