[白俊]1654号:網を切る

5333 ワード
python boj アルゴリズム#アルゴリズム# binary searching テキストリンク

この問題はバイナリ探索で解くことができる.
問題やアルゴリズムを作成すること自体が簡単です.でも提出すると間違って表示されますだからhighを出力した後に値が少しおかしいことを発見しますhighの値を最長の長さにすることは可能ですが、いずれにしてもバイナリ検索なので、何度計算しても変わらないはずなので、1回のShift演算で2^31 - 1を1 << 31 - 1と表示します.
(Sheft演算:左n格子=2^n倍,右1格子=2^-n倍)
しかし、これが問題だとは思わなかった.🙂
コンソールからこれを印刷しました.分かりました.
>>> high = 2 ** 31 - 1
>>> high
2147483647

>>> high = 1 << 31 - 1
>>> high
1073741824
これはhigh値エラー~演算子の優先度が分からないために使用した結果にすぎません😥
Shift演算子の優先度は+、-より低いので、私が望む値を計算するにはカッコを付けなければなりません.
high = (1 << 31) - 1 # 2 ** 31 - 1

high = 1 << 31 - 1 # 2 ** (31 - 1)
正しいコード
import sys

K, N = map(int, sys.stdin.readline().split())
wires = []

for i in range(K):
	wires.append(int(sys.stdin.readline()))

low = 1
high = (1 << 31) - 1
while low <= high:
	mid = (low + high) // 2
	cnt = 0
	for wire in wires:
		cnt += wire // mid
	if cnt < N: # 개수가 모자를 경우 길이를 줄여야 함
		high = mid - 1
	else: # 모자르지 않으면 일단 저장하고 길이를 늘여서 검사
		ans = mid
		low = mid + 1
print(ans)
SQLベース
白駿1167号樹の直径