[BOJ]17451-平行宇宙

5991 ワード
学習ノート ラーニングコーディング 大学生。 greedy boj テキストリンク
https://www.acmicpc.net/problem/17451
質問する
西暦2 XXX年、地球は小惑星と冲突する危机に直面しています!聡明な科学者キパは、平行宇宙で地球に代わる惑星を探す困難な任務を担っている.
私たちは今地球上にいます(=惑星0).様々な要因を考慮して,惑星1,惑星2,...と惑星(n−1)を順番に確認し,地球(=惑星n)に戻ることがコスト的に最適であることが分かった.すべての整数1≦i地球上には「超高速走行機械」という特殊な装置があり、任意に速度を上げることができる.地球を離れるには速度を下げるしかなく、速度を上げることはできない.
次の地域に行くためには、原則として必要な速度を正確に調整しなければならないが、幸いなことに平行宇宙には一定の間隔があるため、必要な速度の正の整数倍も次の地域に移動することができる.また、十分な速度で移動しており、地球の代替惑星に到着した後、それが適切かどうかを知ることができるため、一部の惑星では、到着後に速度を維持し、次の惑星に移動することができます.
すべての1≦i≦nについて、惑星(i−1)から惑星iへの移動に必要な(最小)速度viが与えられる.地球上で向上しなければならない速度を最小限に抑える.
入力
第1行はn(1≦n≦3・105)を与える.
2行目には、n個の整数v 1、v 2、...とvnの間のスペースがあります.すべての整数1≦i≦nに対して、1≦vi≦109を満たす.
しゅつりょく
数を出力します.この数字は地球上で向上しなければならない速度の最高値だ.
サンプルI/O
入力
  • 例1 
    • 5
300 400 500 400 300
  • 例出力1 
    • 900
    Solution
    #include <iostream>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long answer = 0;
    int N;
    cin >> N;
    vector<long long> vec(N);
    for(int i = 0; i < N; i++) cin >> vec[i];
    for(int i = N - 1; i >= 0; i--){
        if(answer <= vec[i]) answer = vec[i];
        else{
            if(answer % vec[i]){
                answer = (answer / vec[i] + 1) * vec[i];
            }
        }
    }
    cout << answer << '\n';
}
    逆算しなければならない.正の方向では計算しにくい問題です.
    いつ何倍のスピードで運転すればいいですか?これは決定すべき問題だ.特定の時点では、要求される速度が増加します.これはこの角度からどれだけ増やす必要があるかという問題です.
    逆にチェックしながら、要求された速度で継続するかどうかを確認しても構いません.でもいつかそうじゃない.速度減少(逆に考えると速度を上げるべき)の時点から現在まで更新されている速度/その時点までの速度+1.何倍のスピードで走るか確認しなければなりませんから.そしてその時刻の速度を乗じる.これにより、すべての時点で満たされる速度が更新され続けます.
    ついに!Generics💫
    Forkkitの紹介:Vue 3フォーム構築フレームワーク