CF R#695 B復習

8152 ワード
practice テキストリンク
B. Hills And Valleys

問題の説明


n個の整数配列を与える.配列内の要素a 1,a 2,...,anだと思って任意の整数j(2<=j<=n−1)に対してaj>aj−1,aj>aj+1を満たす場合、ajは勾配、aj所定の配列が与えられると、解題者はaを1つ選択するだけで必要な値に変換することができる.(変わらないかも)
以上の条件で、n個の整数配列が与えられた場合、山の斜面の水と渓谷の数の和が最も小さい値を配列中に出力してください.

例


入力


6
1 6 2 5 2 10

しゅつりょく


1

5は2に変更され、丘は1つしか残っていません.

私の解答の過程


渓谷と丘の数をどれだけ減らすことができますか?


問題に答えた人はaを1つ変えるしかない.少し変えて影響を受けるのは、選択されたaと両側のaです.例に示すように、1つの点は、3つの丘または渓谷の数を減らすことができる(丘に容易に統一される).しかし,丘数は必ずしも3を減らすことができず,以下のaモードが現れるとそうである.

これにより、所与のaのモードに応じて、0〜3つの丘数を減少させることができる.したがって,aを1つ変えるたびに,どれだけの勾配数を減らすことができるかを決定し,最大減少の場合の勾配数を求める.

どんなパターンがありますか?

  • aj-1==aj+1
    ajにaj−1を代入することにより、aj−1、aj、aj+1を丘陵ではなくすることができる.ajを変更する前に、aj−1、aj、aj+1が丘陵であるかどうかを確認して、どれだけの丘陵を減らすことができるかを決定することができる.
  • aj-1 != aj+1なら
    発生する可能性のあるパターンは、次のようになります.

    aj-1

    簡単な問題解きのトリック


    配列については、勾配の有無を知るのにあまり時間がかかりません.従って、ajは、さらに考慮する必要がなく、山勾配パターンが著しく変化する1)~5)上に位置決めされ、山勾配の有無を判断することによりajを変化させる際に達成できる最小勾配数を求めることができる.
    ここで考えてみると、1)、3)、5)はチェックする必要はありません.各点について、スリップが発生する可能性がある場合をまとめます.

    ここで2),4)の場合は,すべての場合について,常に1),3),5)よりも丘数が少ないか,あるいは同じ結果を生じる.したがって,2),4)にajを置いた場合(aj=aj+1,aj=aj−1)を計算するだけでよい.

    に感銘を与える


    上記の解決策を考えるまでは、そう簡単ではありませんが、問題解決のためのコードを実現すると、かなりのエラーが発生します.次は私がエラーを起こしたときのコードです.
    for(int i=2; i<n+2; i++){
    int bf=0,n1=0,n2=0;
    if (hill_or_vally(arr[i-1], arr[i], arr[i+1])){
        cnt++;
    }
    for(int j=i-1;j<i+2;j++){
        if(hill_or_vally(arr[j-1],arr[j],arr[j+1])){
            bf++;
        }
        if(hill_or_vally(arr[j-1],arr[j-1],arr[j+1])){
            n1++;
        }
        if(hill_or_vally(arr[j-1],arr[j+1],arr[j+1])){
            n2++;
        }
    }
    n1 = min(n1, n2);
    best = max(best, bf-n1);
}
    置換前に2)回であれば,上記のコードを用いて4回であるかどうかを調べる.中間からarr[j]の位置をj−1,j+1に変更することはajが勾配であるか否かを判別する際に問題ではないが,aj−1,aj+1が勾配であるか否かを判別する際に問題であることがわかる.ajのみ移動する場合は丘の数を数えますが、aj-1,aj+1度2),4)では丘が移動したかどうかをチェックします.
    符号化テストの時間制限特性により,コードの整合性を深く考えることが困難であるため,このようなエラーはしばしば発生するようである.最近,比較的複雑な問題を解くためにコードを部分的にテストし,急いでコードを細かく書くほど,最終的には時間を節約する.
    • Javascriptの変数は?
    [2020ココ実習]慶州建設