[伯俊]2110号:ルータ(Python,Pypy)を取り付ける

質問する

私の最初の答え

n,c=map(int,input().split())
x=[]

for i in range(n):
    x.append(int(input()))
x.sort()
mn,mx=(x[1]-x[0]),(x[-1]-x[0]) ###############
result=0
while mn<=mx:
    cnt=1
    mid=(mn+mx)//2 
    v=x[0] 
    
    for i in range(1,len(x)):
        if x[i]>=mid+v:
            v=x[i]
            cnt+=1
            
    if cnt>=c:
        result=mid 
        mn=mid+1
    else:
        mx=mid-1
print(result)

最小ピッチ(mn)をアレイの最初の値と2番目の値の違いとして使用する場合、実際の最小ピッチはこれと異なる可能性があるため、これは正しくありません.したがって、最小間隔を1に設定し、順次増加します.

私の最終的な答え

n,c=map(int,input().split())
x=[]

for i in range(n):
    x.append(int(input()))
x.sort()
mn,mx=1,(x[-1]-x[0])#최소 간격, 최대간격 계산
result=0
while mn<=mx:
    cnt=1 #공유기의 개수, 기준위치를 만족하는 집의 개수
    mid=(mn+mx)//2 #설치 간격(기준 위치)
    v=x[0] #처음집부터 순차적으로 설치
    
    for i in range(1,len(x)):#배열 접근, 인덱스0은 제외
        if x[i]>=mid+v: #현재 집의 위치값(배열값)이 간격보다 크다면
            cnt+=1 #공유기의 개수 1증가
            v=x[i]  #값을 현재 값으로 갱신
            
    if cnt>=c: #적게 설치되어야 함, 간격을 늘려야 함
        result=mid #인접한 공유기 간 최대 거리
        mn=mid+1
    else:#더 설치되어야 함, 간격을 줄여야 함
        mx=mid-1
print(result)#거리 출력

方法

はバイナリ探索問題である.

の特定の間隔に基づいて中間間隔を計算し、ルータをインストールする必要があります.

より多くの

ルータが必要な場合は、中間間隔を減らし、より少ないルータが必要な場合は間隔を増やします.

最小間隔と(mn)最大間隔(mx)が等しくなるまで、

を繰り返します.

の最大間隔(mx)を計算するためには、配列をソートする必要がある.

の最大の中間値(mid)を探すことがこの問題の核心である.