AtCoder Regular Contest 006_C_積み重ね
Greedyはブログにまとめてなかったなと思ったので.ゴミ屋敷の住人必見！？
問題の説明
高橋君が個の箱を積み上げる時に出来る箱の山の最小個数を求めなさい.箱にはその重さ
以下の箱を重ねる事ができる.
条件
考えた事
Greedyの基本は「その場での最善」を繰り返していく事にあります.これを意識して考えるとこの問題は分かりやすいかもしれないです.
では,この問題における「その場での最善」とは何か.結論からいうと今重ねられる山の中で,1番軽いものに重ね,重ねられない場合は山を作る事を繰り返す事となる(方針A).
ここでポイントとなるのはなるべく重ねる事である.例えば8,1,7のように積み上げるとして,8の上に1を載せるのはちょっともったいなく感じるかもしれない(方針B).しかし,それは気のせいでしかない.
上(方針A)と下(方針B)の比較を見て分かる通り,1の上に8を載せようが載せまいが出来る状況は全く同じなのである.
また,
とした場合,上の方針Aでは山が1つなのに対し,下の方針Bでは山が2つ出来てしまう.
一応下の山の方には8が残っているというメリットがあるものの,例えば次に8以下の数字が来た場合,上ならば新しい山を作り,下ならばその8の上に重ねる事で全く同じ状況*1となり,8より大きな数が来た場合は重ねられないため,どちらも山が1つずつ増えてしまい,どちらにせよ8を取っておく意味が全くない事が分かるだろう.
以上から方針Bは却下され,方針Aが最善と分かる.*2大事なのは方針Bが上振れても方針Aと変わらず,順番次第では山一つ増やしてしまう事だ.これが分かれば後は山のてっぺんの数字を記録する配列を作り,てっぺんが変わったら書き換え,新たに山が出来たらcountを増やし,てっぺんの数字を記録するプログラムを書けば容易に解けるだろう.
プログラム
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
for (int i = 0; i < N; i++) {
int we;
cin >> we;
we--;
w.at(i) = we;
}
int count = 0;
for (int i = 0; i < N; i++) {
bool flag = false;
for (int j = w.at(i); j < 100000; j++) {
if (y.at(j) == 1) {
y.at(j) = 0;
y.at(w.at(i)) = 1;
flag = true;
break;
}
}
if (flag == false) {
count++;
y.at(w.at(i)) = 1;
}
}
cout << count << endl;
}
