C++でガソリンスタンド間の最大距離を最小化する方法【二分探索】

問題概要

一本の数直線上にガソリンスタンドがいくつか建っていると考えます。スタンドの位置は stations[0], stations[1], ..., stations[N-1](N は配列の要素数)として与えられます。この状態からさらに K 個のガソリンスタンドを好きな位置に追加し、隣接するスタンド同士の距離の最大値 D をできるだけ小さくしたいとします。目的は、この D の取り得る最小値を求めることです。

たとえば、stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]、K = 9 が入力された場合、出力は 0.5 になります。各区間の長さはすべて 1 なので、各区間に 1 個ずつスタンドを追加すれば、隣接距離の最大値を 0.5 まで縮められるためです。

解法のアプローチ:答えを二分探索する

この問題は「答えそのもの」を二分探索することで効率的に解けます。ある候補値 x について「隣接距離がすべて x 以下になるようにするには、最低何個のスタンドを追加する必要があるか?」を計算できます。この必要個数が K を超えるなら x は小さすぎるため候補を大きい側へ絞り、K 以下なら x は実現可能なので、さらに小さくできないか探索範囲を狭めていきます。

隣接区間の長さが gap のとき、その区間を長さ x 以下に分割するために必要な追加スタンドの数は ceil(gap / x) - 1 です。これを全区間について合計すれば、候補値 x に対する必要追加個数が求まります。

アルゴリズムの手順

• 候補値 x と配列 v を受け取る関数 ok(x, v) を定義します。

• ret := 0 で初期化します。

• i := 0 から v のサイズ未満の間、i を 1 ずつ増やしながら次を繰り返します。

  • ret := ret + ceil((v[i+1] − v[i]) / x) − 1

• ret を返します。

• メイン処理では次を行います。

• low := 0 とします。

• n := s のサイズとします。

• high := s[n−1] − s[0](両端の距離=最大ギャップ)とします。

• high − low ≥ 1e-6 の間、次を繰り返します。

  • mid := (low + high) / 2.0

  • x := ok(mid, s)

  • x > K であれば low := mid(距離を詰めすぎているので下限を上げる)

  • そうでなければ high := mid(実現可能なので上限を下げる)

• high を返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int ok(double x, vector <int>& v){
        int ret = 0;
        for (int i = 0; i < v.size() - 1; i++) {
            ret += ceil((v[i + 1] - v[i]) / x) - 1;
        }
        return ret;
    }
    double minmaxGasDist(vector<int>& s, int K) {
        double low = 0;
        int n = s.size();
        double high = s[n - 1] - s[0];
        while (high - low >= 1e-6) {
            double mid = (low + high) / 2.0;
            int x = ok(mid, s);
            if (x > K) {
                low = mid;
            }
            else {
                high = mid;
            }
        }
        return high;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8,9,10};
    cout << (ob.minmaxGasDist(v, 9));
}

入力

{1,2,3,4,5,6,7,8,9,10}, 9

出力

0.5

計算量について

判定関数 ok() は各区間を一度ずつ確認するだけなので O(N)、二分探索は精度 1e-6 を満たすまで約 log₂(最大距離 / 1e-6) 回繰り返されます。全体の計算量は O(N log(W/ε))(W は座標の幅、ε は許容誤差)となり、N や K が大きい入力でも十分高速に動作します。