Binary search is a powerful method to find the desired value in a sorted sequence, but I have not been used to decide whether the given case should be solved with Binary search.
Not only finding value in an array of a vector but also detecting a case in a certain range can be solved with Binary search.
I think I couldn’t catch it due to the lack of experience.
https://www.acmicpc.net/problem/14452
While solving this problem, finding the time $t$ according to each $k$ was done but I got time-out when I tried to find minimum $k$ by reducing $k$ continuously from the state of $k=N$.
In conclusion, the problem was that $k$ is decreased by one.
It is clear that as $k$ becomes bigger, the time $t$ becomes smaller so with the binary search we can find the minimum $k$ faster.
while(1) {
if (start >= end) {
k = start;
break;
}
int mid = (start + end) / 2;
int t = getT(mid);
if (t > T_max) {
start = mid + 1;
} else {
end = mid;
}
}
Although due to some minor exception handling issues I couldn’t get “correct” at once, I could solve this eventually.