[白俊]1654号:ケーブルを切る(Python)



質問する



私の答え

k,n=map(int,input().split()) #랜선의 개수, 필요한 랜선의 개수
lan=[]
for i in range(k):
    lan.append(int(input()))#랜선의 길이

#랜선의 최대 길이

mn,mx=1,max(lan)

while mn<=mx:
    cnt=0
    mid=(mn+mx)//2
    
    for i in lan:
        if i>=mid:
            cnt+=i//mid
    if cnt>=n:  #만들어야 될 랜선수보다 큰 경우
        mn=mid+1 #최소 길이를 증가
    else:   #만들어야 될 랜선 수보다 적은 경우
        mx=mid-1 #최대 길이를 감소
print(mx)
方法
  • 木を切る問題とほぼ同じ
  • ローカル・ネットワーク線の個数より大きい場合はローカル・ネットワーク線の最小長を増加させ、ローカル・ネットワーク線の個数より小さい場合は最大長を減少させる.