New Year Parties - #611 div3 e
#greedy #min #max #種類数 #数列
解法
min について
1 回の merge で 1 つ数が減る
よって
min(残りの種類数)
= min(元の種類数 - 減らせる種類数)
= min(元の種類数 - max(merge の回数) )
1 2 4 5
で, 2 4 を 3 にすると
1 3 5
1 2 を 2, 4 5 を 5 にしたら
2 5
2 4 を 3 にする問題点は, 1 を無視していること
前から部分問題にする
1 に関して merge 回数を最大にするには, 2, 3 (あれば) を merge に使う
4 以降の部分問題を考えればいい
max について
最近同じ問題やった
小さい数から揃えていって悪くなることはない
