774. Minimize Max Distance to Gas Station

You are given an integer array stations that represents the positions of the gas stations on the x-axis. You are also given an integer k.

You should add k new gas stations. You can add the stations anywhere on the x-axis, and not necessarily on an integer position.

Let penalty() be the maximum distance between adjacent gas stations after adding the k new stations.

Return the smallest possible value of penalty(). Answers within 10-6 of the actual answer will be accepted.

class Solution {
public:
    double minmaxGasDist(vector<int>& st, int k) {
        int n = st.size();
        double l = 0, r = st[n-1]-st[0], m;
        while(l + 1e-6 < r) {
            double m = (l + r) / 2;
            int cnt = 0;
            for(int i = 0; i < n - 1; i++) {
                cnt += ceil((st[i+1] - st[i]) / m) - 1;
            }
            if(cnt > k) l = m;
            else r = m;
        }
        
        return r;
    }
};