Codeforces 388(#228 Div1) A. Fox and Box Accumulation
問題
n個の大きさ、重さが全て同じ箱があって、i番目の箱は自分の上に他の箱をxi個置ける。
一つの箱のすぐ上にはちょうど一つの箱しか置けないとき、
全ての箱をなるべく少ない数の山に分けて積み上げたい。
山の最小個数はいくつか。
制約条件
n≦100
方針
貪欲に弱い奴を上にするように山を作っていけばいいっぽい。
残ってる中で一番弱いやつを取り、その下にできるもので一番弱い奴を取り、…を取れるだけ取り山とする。これを繰り返すという感じ。
何でかというと、
貪欲で取ろうとした奴らy1, y2, ..., ymを分ける場合があったとする。
こいつらはz1, z2の上に積まれるとする。z1≦z2としてよい。
分けなくてはいけないので、m > z1, z2である。
でもそうすると、ym≧m-1だから、ym≧z1, z2
ym>z1, z2だとすると貪欲に取ったという仮定に反するから結局ym = z1またはym = z1 = z2
んでもこれって結局z1を取り除いてz2の上に置くのと同じ。
(z2の上におけないとすると分けて置く仮定に反するからz2の上には必ず置ける)
なのでそういう場合があったら貪欲法でも必ず置けるので考えなくてよい。
以上より貪欲法で上手くいくことがわかる。
int main(){ int n; int ans = 0; multiset<int> s; cin >> n; rep(i, n){ int a; cin >> a; s.insert(a); } while(s.size()){ ans++; int cnt = 0; while(1){ set<int>::iterator it = s.lower_bound(cnt); if(it == s.end()) break; cnt++; s.erase(it); } } cout << ans << endl; return 0; }