問題の説明

N個のマンションが一列に並んでいる.一部のマンションの屋上には4 g基地局が設置されている.技術の発展に伴い、5 gに対する需要はますます高くなり、4 g基地局を5 g基地局に変えたいと思っています.しかし、5 g基地局は4 g基地局より転送範囲が小さく、4 g基地局が5 g基地局に変更されると、一部のマンションでは電波が届かない.
例えば、11棟のマンションがずらりと並び、[4,11]2棟目のマンションの屋上には4 gの基地局が設置されている.この4 g基地局が電波到達距離を1人5 g基地局に変更すると、全てのマンションに電波を送ることができない.(伝播距離がWの場合、基地局のあるマンションから両側に伝播距離を伝播することができる.)

初期には、1,2,6,7,8,9号マンションでは電波が伝播しなかった.

1、7、9棟目のマンションの屋上に基地局を設置すれば、全てのマンションに電波を送ることができる.

3つのマンションよりも多くの屋上に基地局を設置すれば、すべてのマンションに電波を送ることもできる.

このとき,基地局を最低限に設定し,すべてのマンションに電波を伝送する.上記の例では、すべてのアパートに電波を送信するには、少なくとも3つのアパートの屋根に基地局を設置しなければならない.
マンションの個数Nは、現在基地局のマンションの番号が設定されている1次元配列局であり、電波の到達距離Wをパラメータとした場合、全てのマンションに電波を伝達するために増設する基地局個数の最大値のコールバック関数を完了してください.

せいげんじょうけん

N:2億2000万以下の自然数
サイトサイズ:10,000以下の自然数
サイトは昇順に並べられ、配列の数はNの自然数に等しいか、または小さい.
W:1000以下の自然数

プール（非効率）

from math import ceil

def solution(n, stations, w):
    answer = 0
    apartments = [0 for _ in range(n)]
    for s in stations:
        for i in range((s-1)-w, s+w):
            if i >= 0 and i < n:
                apartments[i] = 1
    cnt = 0
    for i in apartments:
        if i == 0:
            cnt += 1
        else:
            answer += ceil(cnt / (1+2*w))
            cnt = 0
    answer += ceil(cnt / (1+2*w))
    return answer

マンション配列、

電波が通過する箇所は1で

と表記する.
各セグメント

の長さは

である.

発射塔は1つの範囲1+2*wに分けて、それからアップロードします
そうすると、テストは合格しますが、効率的にすべてタイムアウト・・

別の解釈

from math import ceil
def solution(n, stations, w):
    answer = 0
    start = 0
    for s in stations:
        left = (s-1)-w  # 전파 범위중 가장 왼쪽을 left라고 함
        # left - start는 전파 범위에 안들어 가는 구간이고 1+2*w는 송신탑 하나의 최대범위임
        answer += ceil((left - start) / (1+2*w))
        start = s+w
    answer += ceil((n - start) / (1+2*w)) # 마지막 스타트에서 끝까지 구간 
    return answer

ビットのプールをインデックスとして

にアクセス

駅を順番に迂回し、範囲の一番左側、

左-start電波が通じない区間長

を求める

以降、同じ発射塔を1+2*wの範囲に分け、

最後のsの後から尾までの長さを計算するのを忘れないでください!