Codeforces Round #802 (Div. 2) D. River Locks

Problem - D - Codeforces

D를 이분 탐색 안 하고 풀 수 있길래 적어본다.

먼저 파이프를 맨 앞쪽부터 여는 게 가장 좋은 방법인 건 그냥 바로 알 수 있다.

그러면 답은 간단해진다.

x개를 열었을 때 모든 버킷을 채우기 위해 걸리는 시간을 x = 1부터 나열해 보면

1개 열었을 때 걸리는 시간

2개 열었을 때 걸리는 시간

3개 열었을 때 걸리는 시간

...

n개 열었을 때 걸리는 시간

이 수열은 증가하지 않는 수열이다.

따라서 t초안에 모든 물을 채우게 할 수 있는 최소의 파이프의 수를 이분 탐색으로 해결할 수 있다.

n개를 열어서 모든 버킷을 걸리는 시간보다 더 적은 t가 주어질 경우에 답이 없으므로 -1이 답이다.

이 구문을 잘 생각해 보면 어차피 더 적은 t가 주어질 경우에 -1로 예외처리를 한다.

따라서 이후에는 그냥 (모든 버킷의 공간) / t의 값을 답으로 적으면 된다. ( 반올림 잊지 말자 )

결국 이분 탐색도 할 필요도 없다.

n개의 파이프를 열었을 때 전부 채우는 데 걸리는 시간보다 적게 주어질 경우 -1

아닐 경우 (모든 버킷의 공간) / t ( 반올림 )을 출력해 주면 된다.