I decided to solve 1 problem 1 day to acquire programming skill.
Binary Search
N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split())) + [L]
def greedy_cut_try(x, threshold):
temp = 0
now_cut_num = 0
end_point = -1
for i in range(N):
#N-1までなのは、切れ目が
if x[i] - temp >= threshold:
#切ったものが閾値を超えていたら
temp = x[i]
#細切れは手元にない
now_cut_num += 1
#切った回数を記憶
else:
pass
#まだ切らない
if now_cut_num == K:
break
#K回切ったら終わり
if now_cut_num == K and L - temp >= threshold:
return 1
#K回切れていて 最後の切れ端も閾値を超える
else:
return 0
def binary_search(x):
#二分探索、解が一直線上にあり、有界
l = 0
r = L
#上限と下限を指定する
while r - l > 1:
mid = int((l+r)/2)
#中点を取って
if greedy_cut_try(x, mid) == 1:
l = mid
else:
r = mid
#更新していく
return l
def main():
score = binary_search(A)
print(score)
main()
- 二分探索の気持ちは、境界を決めましょう、ということ。
- そして、観測区間を2分することで、解像度を上げましょう、ということ。
- 境界の片方では、成り立ち、もう片方では、成り立たない、というものを考えるときに使える。
- 最大、最小、といった考え方は、上限、下限、という考え方と繋がりがある。
- つまり、そこが、境界となる。よって、二分探索にもってこいである。
- 似た話では、限界、というのは、境界のことであると言える
- 生体内に投与できる物質Xの量の限界（最大値）を求めたいとき、こういう二分探索を使うと、費用や時間を節約出来て、良いかもしれない。
- ただし、その結果を見てから、次を行う、ということをしているので、一気に出来るわけではない。これは弱点かもしれない
