Note that the corresponding "decision problem"--determine whether $M$ buses suffice if every cow waits at most $T$ minutes--can be solved efficiently by a greedy algorithm. Additionally, the decision problem is monotonic in $T$: that is, if a maximum waiting time of $T$ is impossible, then no smaller maximum waiting time will be possible.

This means that we can find the smallest possible maximum waiting time by binary searching for the answer. We start off knowing that the answer is in some range $[l,r]$. Then we check whether $M$ buses suffice if every cow waits at most $T = (l+r)/2$ minutes. If yes, we can narrow the range to $[l, (l+r)/2]$; if no, we can narrow the range to $((l+r)/2, r]$. Then we recurse. In our case, we have an initial range $[0, 10^9]$ (since the optimal waiting time must be nonnegative, but we can clearly get away with only one bus if every cow waits $10^9$ timesteps), so the binary search will terminate in about $\log_2 10^9 \approx 30$ iterations.

Now, we must solve the decision problem. As mentioned, it lends itself to a greedy algorithm. Fix some desired maximum waiting time $T$. Suppose that we want to find the minimum number of buses needed so that every cow waits at most $T$ timesteps. Then the first bus cannot leave more than $T$ timesteps after the first cow arrives. But there's also no point to leaving earlier! If at most $C$ cows have arrived by this point ($T$ timesteps after the arrival of the first cow), then the first bus simply takes these cows. Otherwise, the bus ought to take the first $C$ cows who arrive (since these cows "expire" soonest).

So the first bus takes some prefix of the cows: either the first $C$ cows, or all cows who arrive at most $T$ timesteps after the first cow. After this bus has left, the same argument applies to the second bus and the remaining cows. So for each bus, we can figure out the optimal set of cows it can take. If after $M$ buses, not all cows have left, then $T$ is not a feasible maximum waiting time. Otherwise, it is.

#include <iostream> #include <algorithm> using namespace std; int N,M,C; int t[100000]; bool pos(int wait) { int wagons = 1; int firstArrival = t[0]; int firstIndex = 0; for(int i=1;i<N;i++) { if(t[i] - firstArrival > wait || i + 1 - firstIndex > C) { wagons += 1; firstArrival = t[i]; firstIndex = i; } } return (wagons <= M); } int binSearch(int low,int high) { if(low == high) return low; if(low + 1 == high) { if(pos(low)) return low; return high; } int mid = (low+high)/2; if(pos(mid)) return binSearch(low,mid); else return binSearch(mid+1,high); } int main() { cin >> N >> M >> C; for(int i=0;i<N;i++) cin >> t[i]; sort(t,t+N); cout << binSearch(0, 1000000000) << '\n'; }