[競技プログラミング][PHP][AtCoder]積み重ね

C - 積み重ね

時間制限 : 2sec / スタック制限 : 10MB / メモリ制限 : 64MB

問題文

高橋君はもう大人なので、親元を離れて一人暮らしをすることにしました。
トラックから引越し先の部屋へと荷物のダンボールを運びたいのですが、
部屋の床がダンボールで埋まってしまうと、今日高橋君が寝るための布団がひけません。
そこで、1 箱ずつ広げて置くのではなく、ある程度ダンボールを積み重ねた山を作ることにしました。
しかし、ダンボールには重さが決まっており、
下にあるダンボールよりも重いダンボールを上に積み重ねると下のダンボールが潰れてしまいます。

図(※略)：下にあるダンボールは上にあるダンボール以上の重さでなければならない

トラックから運ぶ順にダンボールの重さが与えられるので、ダンボールを潰さないような積み重ね方を考えなさい。
そして、その積み重ねた山の個数が最小となる場合の山の個数を求めなさい。

入力

入力は以下の形式で標準入力から与えられる。

N
w₁
w₂
:
:
w_N

入力は N+1 行ある。
1 行目には、ダンボールの個数を表す整数 N(1≦N≦50) が与えられる。
2 行目からの N 行には、i+1(1≦i≦N) 行目に i 番目に運ぶダンボールの重さを表す整数 w_i(1≦w_i≦100,000) が与えられる。

出力

ダンボールを順番に運び、上のダンボールが下のダンボールと同じ重さまたはそれよりも軽くなるように積み重ねたときに、
できるダンボールの山の数の最小値を標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

出典

C: 積み重ね - AtCoder Regular Contest #006 | AtCoder

回答

AtCoder/arc006_3.php at master · wada811/AtCoder · GitHub

<?php
fscanf(STDIN, "%d", $n);
for($i = 0; $i < $n; $i++){
    fscanf(STDIN, "%d", $inputs[]);
}
$Mt = array();
for($i = 0; $i < $n; $i++){
    $pos = 0;
    for($j = 0; $j < count($Mt); $j++){
        $pop = $Mt[$pos][count($Mt[$pos])-1];
        if($pop < $inputs[$i]){
            $pos = $j;
        }
    }
    if($Mt[$pos][count($Mt[$pos])-1] >= $inputs[$i]){
            $Mt[$pos][] = $inputs[$i];
    }else{
            $Mt[][] = $inputs[$i];
    }
}
echo count($Mt).PHP_EOL;
?>

山のてっぺんのダンボールの最大重量が入力より軽い場合は載せられないので$posを変える。
後ろの山の方は積めなかったダンボールを積んだ山なので
基本的に後ろの山が重くなっているのでできるだけ重いダンボールに重い荷物を載せる。
最後まで走査して載せられるかをチェックしたら載せ、載せられなかったら新たに山を作る。

動きを忘れていたけどIdeone.comでログ出力したら思い出した。