Minimize Max Distance to Gas Station

Minimize Max Distance to Gas Station

#include<bits/stdc++.h>
using namespace std;

struct Interval
{
  Interval (int d): num(d), den(1), dist(d){}

  bool operator< (const Interval &d) const {return dist < d.dist;}
  double num,den, dist;
  void update(){den++, dist = num/den;}
};

template<typename T>
priority_queue<T> make_priority_queue (vector<int>& v){
  vector<int> t(v.size());

  adjacent_difference(v.begin(), v.end(), t.begin());
  t.erase (t.begin());
  return priority_queue<T> (t.begin(), t.end());
}

double minmaxGasDist(vector<int>& stations, int k)
{
  auto PQ = make_priority_queue<Interval> (stations);
  double mx_dist = (stations.back() - stations.front())/static_cast<double> (k+1);

  while(k){
    auto top = PQ.top();
    PQ.pop();
    while(k && (top.dist >= PQ.top().dist || top.dist > mx_dist)){
      top.update();
      k--;
    }
    PQ.push(top);
  }
  return PQ.top().dist;
}

int main()
{
     #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
  #endif

    vector<int>V;
    int n,k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
      int x;
      cin >> x;
      V.push_back(x);
    }
    cout << minmaxGasDist(V, k)<<endl;

}

Share: