[ラーニングテストエンコーディング]ローカルエリアネットワークの切断

ソース:https://www.acmicpc.net/problem/1654

もんだいぶんせき

問題の条件が表示された場合、時間は2秒、Kは10000以下に制限されます.したがって,複雑度がO(n^2)に達することは許容されるが,この問題は二分ナビゲーションでしか解決できない.理由は次のとおりです.
特定の整数値は、

データリストからのみエクスポートする必要があります.

整数値がデータ・リストに存在する値であることは保証されないため、異なる方法で値をエクスポートする必要があります.

の制約条件を分析すると、これは最適な二分探索であることがわかります.

この問題は従来の木の剪断問題と解法とよく似ている.コードをチェックします.

コードを確認しましょうか?

import sys

input = sys.stdin.readline

K, N = map(int, input().split())
line_length_list = []

for _ in range(K):
    line_length_list.append(int(input()))
    
start, end = 1, max(line_length_list)

# 이분 탐색 시작
while start <= end:
    sum = 0
    mid = (start + end) // 2
    
    for length in line_length_list:
        sum += length // mid
        
    if sum >= N:
        start = mid + 1
    else:
        end = mid - 1
        
print(end)

昔の木切り問題と解答方法は同じだったので、簡単に説明するだけです.
startは1,endはローカルエリアネットワーク線の最大長であり,次いで二分ナビゲーションを開始する.
ローカルエリアネットワーク線の場合、midで割った残りの値が得られるため、長さをmidで割った割合がsumに反映される.
sumの値に応じてstartまたはendの値を調整できます.

sumがNより大きい場合は、もう少し短く切ることができるので、startの値は

に調整することができます.

sumがN未満の場合:少し短い必要があるためend値

を調整することができる.
従って、最終出力endは問題を解決することができる.