👏

AtCoder Beginner Contest 339 C - Perfect Bus 備忘録 PHP

2024/05/06に公開

AtCoder

tech

PHPで解いています。

問題はこちら。

解のポイント

この問題におけるNGとは何か？を考える。
→途中で乗客がマイナスになるのはNG
→マイナスにならないように最初に乗っている乗客を設定しないといけない

それならば…
途中のマイナスの絶対値の最大＝最初に乗っている乗客
という事になる。

そこで途中のマイナスを更新していく変数を設定する。

// マイナスになった場合のマイナス最大値を更新していく変数：初期値は0
$minus = 0;

また最終的には合計人数を出さないといけないため、最初の乗客以外の乗客人数を累計しておくための変数を設定し、配列を１つ処理するごとに一緒に更新していく。

// 途中経過の合計人数を格納する変数
$sum = 0;

C問題は計算量がカギである→１回の配列処理のなかで数値を積み上げ結果を出す方法を考える

全体コード

<?php

$N = trim(fgets(STDIN));


// マイナスになった場合のマイナス最大値を更新していく変数：初期値は0
$minus = 0;

// 数を取得
$a = trim(fgets(STDIN));
// 数を配列にする
$arrays_a = explode(" ", $a);
// 途中経過の合計人数を格納する変数
$sum = 0;

// print_r($arrays_a);

foreach ($arrays_a as $value) {
    $sum += $value;
    if ($sum < 0) {
      if($sum < $minus) {
        $minus = $sum;
      }
    }    
}

// マイナス数値を絶対値に変換:$result_minusは最初の乗客の最小値である
$result_minus = $minus * -1;

//最初の乗客の最小値と後の乗客の累計を合計する
echo $result_minus + $sum . PHP_EOL;

解のポイント

全体コード

Discussion