[テストコード]変なバー

3963 ワード
コーディングテスト ダブルポインタ テキストリンク
ソース:https://www.acmicpc.net/problem/13702

まず問題を分析しましょう。


時間制限は1秒、メモリ制限は512 MBです.Nは10000に制限され,理論的には1秒に制限されるので,O(N 2)O(N^2)O(N 2)の複雑さを達成できる.
ただし、できるだけ多くの米酒を割り当てる容量が必要なため、「二分法」ナビゲーションを実行する必要があります.そこで,O(N 2 logN)O(N^2 logN)O(N 2 logN)の複雑さで問題を解決する.
問題を解くのは簡単ですから、すぐ私についてきてください.

まずコードを見てみましょう

import sys

# 13702 이상한 술집
input = sys.stdin.readline

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

for i in range(N):
    alchohol_list.append(int(input()))
    
start, end = 1, max(alchohol_list)

while start <= end:
    mid = (start + end) // 2
    count = 0
    
    for alchohol in alchohol_list:
        count += (alchohol // mid)
    
    if count >= K:
        start = mid + 1
    else:
        end = mid - 1
        
print(end)
countは累積変数であり、何回に分けることができますか.
今回のナビゲーションでは、alchohol listをcountに線形にナビゲートし、countの値に基づいてstartを増やしたりendを減らしたりして、今回のナビゲーションを実行します.
最後にendを出力して問題を終了します.
CFIleDialog複数のファイルを開く
深いコピーの現代的な書き方