白俊-2212号センサー

4401 ワード
greedy algorithm テキストリンク
2212号センサー

👏 key point


実際、これは問題を理解するのにかなり時間がかかる問題です.
たとえば、入力されたリストは1 6 9 3 6 7です.
座標で次のように表します.

Q.集中局が1つしかなかったらどうなりますか?
A.1〜9の間の全てのセンサは検出する必要があるので、受信可能領域の長さは8である.
Q.では、中国に2つあるとどうなりますか?

A.このように区間が最も長い区間を除き、受信可能領域の長さは5であり、最も短い集中局を設けることができる.
そこで,筆者はセンサを昇順に並べて座標上の平面を実現した.
サイドセンサ間の距離を求め,アレイ表現の距離を生成した.次にソートし、最大値のプロシージャを繰り返します.(k-1)
したがって,残りの区間の和が受信可能領域の最大値である.詳細はコードを見ればわかります.

🎂 コード#コード#

n = int(input())

k = int(input())

sens = list(map(int, input().split()))

if n <= k:
    print(0)

else:    
    #센서들을 오름차순으로 정렬
    sens.sort()

    distance = []

    #distance = 옆에 있는 센서들끼리의 거리들을 구한 배열
    for i in range(1,n):
        distance.append(sens[i] - sens[i-1])

    distance.sort()
    #distance를 정렬하여 k-1만큼 pop
    for _ in range(1,k):
        distance.pop()

    #남은 구간들의 합 = 수신 가능영역의 최솟값
    print(sum(distance))
RxAndroidコンビネーションRetrofitによるファイルアップロードpost getの実現
(サムスン)-ギア(14891)