【区間の積】STEP: 3 最短の区間 (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【区間の積】STEP: 3 最短の区間 (paizaランク B 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
この問題もテストケースに巨大な数値が設定されており、二重ループを使用した総当たりでの探索はタイムオーバーとなります。この問題を攻略する為には「しゃくとり法」を使用しなければなりません。「しゃくとり法」についてはこちらの記事を確認してください(;^ω^)
本当このアルゴリズムを考慮した問題シリーズ難しい(>_<)
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; $m = $input[1]; $array = explode(" ",trim(fgets(STDIN))); //配列の作成 $a = 0; $ans = 0; $range = $n; for($i = 0;$i < $n;$i++){ //しゃくとり法で再誕区間の検証処理 $ans += $array[$i]; if($ans >= $m){ $test = $i - $a; if($range > $test){ $range = $test; } while($ans >= $m){ $ans -= $array[$a]; $a++; if($ans >= $m){ $test = $i - $a; if($range > $test){ $range = $test; } } } } } if($range == $n && $ans < $m){ echo "-1"; } else { echo $range + 1; } ?> |
