[プログラマ-レベル3]基地局の設定

完全な問題の説明

問題の概要

N個のマンションが一列に並び、各マンションに基地局を設置できる.各基地局から送信される電波の到達距離をWと呼ぶと、基地局のあるマンションに基づいてW数の電波を両側に送信することができます.
NとWと、現在基地局が設置されているマンションの番号を含む1次元配列のサイトがある場合、基地局を最小限に増やしながら、すべてのマンションに電波を伝送しようとします.増設が必要な基地局数の最大値を返す関数を作成してください.
<制限>
N:2億2000万以下の自然数
サイトサイズ:10,000以下の自然数
サイトは昇順に並べられ、配列の数はNの自然数に等しいか、または小さい.
W:1000以下の自然数

例えば、上の図に示すように、N=11、States=[4,11]、W=1である.

この3つの基地局を増やすことで、すべてのアパートに電波を伝えることができます.△3つ未満の基地局を増やすことで、すべてのマンションに伝播することはできない.

必要条件を把握する

完全なナビゲーションで非効率な問題を解決できない場合や、問題を適切な部分に分割する方法が分からない場合は、「コンポーネントに絶対に含まない値」または「コンポーネントに含まなければならない値」を決定することが望ましい.この問題を解決する最も簡単な方法は、問題の悪化を招く可能性のある必要条件を決定することである.
まず、答えはすべてのアパートに伝播した状態を含まなければならない.この場合,解を構成するために必要な条件は何でしょうか.私たちはまだ答えが何なのか分かりませんが、私たちははっきり見ることができます.
最初の基地局の位置は(1+w)号マンションを超えてはいけない.
最初の基地局が(1+w)号マンションの後ろに設置されている場合、少なくとも1号マンションは伝播されず、危害を及ぼさない.では最初の基地局の位置は、可能な場所は1番~(1+w)号マンションです.
このうち(1+w)号マンションに設置する場合は、1+w号マンションに設置することが望ましい.これにより、1~w号マンションの電波到達範囲をすべてカバーし、より多くの電波を後方に伝達することができる.
しかし、最初に設置された基地局のうち、(1+w)号よりも早いマンションに1つの基地局が設置されている場合、その基地局を最初の基地局としなければならない.
これにより、第1の基地局の位置はmin(station[0],1+w)と決定される.では、今からi基地国の位置を考えてみましょう.
i第1の基地局の位置に対する制約条件は、第1の基地局の位置を選択することとあまり変わらない.
i第1の基地局は、(i−1)第1の基地局(2 w+1)からの距離内にある必要がある.
2つの基地局間の距離差が(2 w+2)を超えると、伝播を受け入れられないマンションが1つ以上現れるからだ.この場合、最適な位置は依然として(i−1)第2の基地局(2 w+1)からの位置である.しかしながら、同様に、(i−1)第2の基地局とその基地局(2 w+1)との距離内に既存の基地局[j]が存在する場合、基地局[j]をi第2の基地局とするべきである.
以下にまとめる.

第1の基地局

min( stations[0], 1 + w )

i第2の基地局

min( station[j], loc[i - 1] + 2w + 1 )
(但し、局[j]はloc[i-1]に続く最小インデックス局である)

絶対的に有害でない限り、適切な危害を構成する必要条件を一つ一つ満たすことができます.
実装中は、最後の基地局の設置場所を確認する際に発生するエラーに注意するだけです.
ある基地局iの最適な設置位置(nextStatoin)が(n+w)を超えると、(i−1)第1の基地局がn号マンションに伝播できることを意味するが、i個の基地局の設置位置が(n+w)以下であると算出される.(i-1)第1の基地局はマンション全体をカバーすることができず、n号マンションに基地局を増設しなければならない.

コード#コード#

class Solution {
    public int solution(int n, int[] stations, int w) {
        int answer = 0;
        int nextStation = w + 1;
        
        for(int station : stations){
            while(station > nextStation){
                answer++;
                nextStation += w * 2 + 1;
            }
            nextStation = station + w * 2 + 1;
        }
        
        while(nextStation <= n + w){
            answer++;
            nextStation += w * 2 + 1;
        }
        
        return answer;
    }
}