Proficient.
Put your skills to the test.

Problem summary

N towns lie in order on a single road. Choose K towns for ambulance stations to minimize the maximum distance from any town to its nearest station.

Constraints

1 ≤ K ≤ N ≤ 1000; each consecutive distance is an integer in [1,1000].

Worked example

An independently prepared example for this explanation.

4 2
3 5 2

3

Solution analysis

1. Build increasing town coordinates with the first town at zero. For a proposed radius D, take the leftmost uncovered town x and put a station at the rightmost town whose coordinate is at most x+D.
2. This station covers every town up to station+D. Skip these towns and repeat. The greedy number of stations is the minimum required for this radius, so D is feasible exactly when at most K stations are used.
3. In the example coordinates are 0,3,8,10. Radius 3 permits stations at 3 and 10. Radius 2 cannot jointly cover the first two towns, and still needs a station near the final pair. Binary search therefore returns 3.

Why it works

Any solution covering the leftmost uncovered town must use a station no farther right than the greedy station. Replacing that station by the greedy choice retains coverage of the leftmost town and cannot lose coverage of a later town. Repeating this exchange proves greedy optimality. Feasibility is monotone in D, so binary search finds its smallest true value.

Watch out. Stations must be at towns, not arbitrary points. Using fewer than K stations is sufficient because additional stations cannot worsen coverage.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    // Compute the exact archive answer using the method explained above.
    int n,k;
    cin>>n>>k;
    vector<int>x(n,0);
    for(int i=1;i<n;i++){
        int distance;
        cin>>distance;
        x[i]=x[i-1]+distance;
    }
    auto feasible=[&](int radius){
        int first=0;
        int used=0;
        while(first<n){
            int center=first;
            while(center+1<n&&x[center+1]-x[first]<=radius){
                center++;
            }
            int limit=x[center]+radius;
            while(first<n&&x[first]<=limit){
                first++;
            }
            used++;
        }
        return used<=k;
    };
    int low=0;
    int high=x.back();
    while(low<high){
        int middle=low+(high-low)/2;
        if(feasible(middle)){
            high=middle;
        }
        else{
            low=middle+1;
        }
    }
    cout<<low<<'\n';
}