白駿2110題/本369 p

質問する

に答える

初見

適当な数を探す探索を思い出したかまぼこ問題のパラメータ検索
そうでしょう?

「適切」の基準は、「最も隣接する2つのルータ間の距離が最大」である可能性があります.

家は一直線上にあり、マイナスして割引を加えて街に活用します.

しかしルーターが2つではなくC個であれば手で考えるのが早いです.

このまま半分に分けましょう.

ソリューション

パラメトリックサーフェスタイプ

バイナリナビゲーションで「2つの最も隣接するルータ間の距離」を調節でき、一瞬ごとに実際にルータを設置し、Cより多くのルータを設置できるかどうかをチェックし、問題解決

「2つの最も隣接するルータ間の距離」の最値であるため、ルータの数がCより大きい場合は「2つの最も隣接するルータ間の距離」の値を増やし、より大きな値を再探索して成立しているかどうかを確認する.

例)
5軒の家の座標は[1,2,4,8,9]、ルータの最小数C=3

最も隣接する2つのルータ間の距離(gap)は、1〜8とすることができる.

最大gap=8

最小gap=1

1)範囲は1～8なので、ギャップ値は中間値4に設定します.
前面から取り付け、[1,2,4,8,9]のように取り付けます.
これで2つのルータしかインストールできません.
C=3なので、さらに隙間を狭める必要があります.
範囲を[1,3]に変更します.

2)は1～3の範囲で、gapの値を中間値2に設定します.
前面から取り付け、[1,2,4,8,9]
C=3ですが、C=3以上の値です.
現在のgapを保存した後、gapの値を増やして、gapがより大きい場合も可能であることを確認する必要があります.したがって、範囲が[1,3]の場合、範囲を[3,3]に変更する.

3)は3～3の範囲であり、gapの値は中間の3に設定する.この場合、C=3であるが、C=3は1つ以上の値であるため、現在のgapを保存した後、gap値がgapより大きくなった場合であるかどうかをチェックする必要がある.
現在の範囲は3～3で、これ以上範囲を変更することはできません.
->したがって、gap=3が最適な場合.

コード#コード#

# 집의 갯수 N, 공유기의 최소 갯수 C 입력받기
n, c = list(map(int, input().split(' ')))

# 전체 집의 좌표 정보를 입력받기
array = []
for _ in range (n) :
	array.append(int(input()))
array.sort() # 이진탐색 수행을 위해 정렬 수행

start = array[1] - array[0] # 집의 좌표중에 가장 작은 값
end = array[-1] - array[0] # 집의 좌표중에 가장 큰 값
result = 0

while (start <= end) :
	mid = (start+end) // 2 # mid는 가장 인접한 공유기사이의 거리(gap)를 의미
	value = array[0]
	count = 1
	# 현재의 mid값을 이용해 공유기를 설치
	for i in range(1, n) # 앞에서부터 차근차근 설치
		if array[i] >= value + mid :
			value = array[i]
			count += 1
	if count >= c : #C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가
		start = mid + 1
		result = mid #최적의 결과를 저장
	else : #C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소
		end = mid - 1

print(result)

に感銘を与える

遠いですか.まだよく分かりません.
[]手描き
[]ストライク