https://www.acmicpc.net/problem/18320
18320번: Loan Repayment
Farmer John owes Bessie $N$ gallons of milk ($1\le N\le 10^{12}$). He has to give her the milk within $K$ days. However, he doesn't want to give the milk away too quickly. On the other hand, he has to make forward progress on the loan, so he must give Bess
www.acmicpc.net
X가 1이면 항상 가능하다. X가 N이면 1 * K < N 이므로 항상 불가능하다.
따라서 먼저 이분탐색을 생각해 볼 수 있다. O(KlogN)
당연히 이분탐색만 쓰면 시간초과가 난다. 하지만 N이 1e12이므로 sqrt(N)풀이가 가능할 것이다.
Y가 같은 day들을 O(1)에 처리할 수 있다고 가정하면
1 + 2 + ... + sqrt(2N) >= N 이므로 서로 다른 Y는 최대 sqrt(2N)이라서 O(sqrt(N)logN)이 가능하다.
Y가 같은 day들을 O(1)에 처리하는 방법은
a = (N - G) // X, b = (N - G) % X라고 하면 Y가 같은 day들의 개수는 b // a + 1이 된다.
이제 G에 그 개수 * (b // a + 1)을 더하면 된다.