[Baekjoon][Python]18310号アンテナ

18310アンテナ

質問する

に答える

問題を見ると,バイナリ探索を用いた解決策を思いつく.
まず,中央値を基準として左右の路の和を求め,より小さな方向に移動する.時間の複雑さは完全バイナリ検索より高いが,良い方法を考えた.
しかし、問題の主な条件を逃したため、解決が複雑すぎるようだ.つまりアンテナは家のある場所にしか存在しないということです.

import sys

def totalSum(loc, locations):
    totalSum = 0
    for location in locations:
        totalSum += abs(loc-location)
    return totalSum
def findPoleLocation(locations, n):
    poleLocation = locations[n // 2]
    if poleLocation - 1 <= 0 or poleLocation + 1 > locations[-1]:
        return poleLocation
    startSum = totalSum(poleLocation, locations)
    left = totalSum(poleLocation - 1, locations)
    right = totalSum(poleLocation + 1, locations)
    flag = 0
    minSum = 0
    if startSum >= left:
        flag = -1
        poleLocation -= 1
        minSum = left
    elif startSum <= right:
        return poleLocation
    elif startSum > right:
        flag = 1
        poleLocation += 1
        minSum = right

    while True:
        sumData = totalSum(poleLocation + flag, locations)
        if minSum >= sumData:
            if flag == 1:
                return poleLocation
            minSum = sumData
            poleLocation += flag
        else:
            return poleLocation

# 집의 수
N = int(sys.stdin.readline())

locations = list(map(int, sys.stdin.readline().split()))
locations.sort()

上のコードでは、アンテナだけを家のある場所に配置すれば、少し時間を短縮できますが、もっと良いアイデアを思いつきました.
整列した後に中点を選択します.
すなわち,中間値を選択した場合,距離の和が最小となる.
したがって、以下の非常に簡単なコードを使用することができる.

import sys
N = int(sys.stdin.readline())
locations = list(map(int, sys.stdin.readline().split()))
locations.sort()
print(locations[(N - 1) // 2])

n/a.結論

この問題から感じたのは、問題をもっと詳しく読んで、もっと創意的に考えたいということです.ソートは核心的な問題です.