C++で各都市から最寄り駅までの最大距離を求めるアルゴリズム

概要

0からN-1までの番号が付けられたN個の都市と、駅が設置されている都市のリストが与えられたとき、「任意の都市からその最寄り駅までの距離」の最大値を求めるのが本課題です。なお、駅のある都市は任意の順序で与えられる点に注意してください。

入力例

numOfCities = 6, stations = [2, 4]

出力

2

入力例

numOfCities = 6, stations = [4]

出力

4

• 1つ目の例では、6つの都市が存在し、駅がある都市が緑色で強調表示されています。この場合、最寄り駅から最も遠いのは都市0で、その距離は2です。したがって、最大距離は2となります。

• 2つ目の例では、最寄り駅から最も遠いのは都市0で、その距離は4です。したがって、最大距離は4となります。

解法のアプローチ

この問題には、次の3つの場合が考えられます。

• 最も遠い都市が2つの駅の間に位置する場合

• 最も遠い都市が最初の駅より左側に位置する場合

• 最も遠い都市が最後の駅より右側に位置する場合

これらのケースをすべてカバーするために、以下のアルゴリズムを実装します。

• サイズN(都市数)のブール型配列をfalseで初期化し、駅がある都市の要素をtrueに設定します。

• 変数distを0で初期化します。さらに、別の変数maxDistを「駅がある最初の都市の番号」で初期化します(2番目のケースに対応)。

• すべての都市を先頭から順に走査します。

• 現在の都市に駅がある場合は、maxDistに「(dist + 1) / 2」と「maxDist」のうち大きい方を代入し(1番目のケースに対応)、distを0にリセットします。

• 駅がない場合は、distを1ずつ増加させます。

• 最後に、distとmaxDistのうち大きい方を返します(3番目のケースに対応)。

実装例(C++)

// 任意の都市とその最寄り駅との間の
// 最大距離を計算するC++プログラム
#include<bits/stdc++.h>
using namespace std;

// 任意の都市とその最寄り駅との間の
// 最大距離を計算する関数
int findMaxDistance(int numOfCities1, int station1[], int N){
    // ブール型配列を初期化
    bool hasStation[numOfCities1 + 1] = {false};
    // 駅がある都市にtrueを設定
    for (int city1 = 0; city1 < N; city1++){
        hasStation[station1[city1]] = true;
    }
    int dist1 = 0;
    int maxDist1 = INT_MAX;
    // 駅がある最初の都市の番号を取得
    for(int i = 0; i < N; i++){
        maxDist1 = min(station1[i], maxDist1);
    }
    // 全都市を走査して最大距離を更新
    for (int city1 = 0; city1 < numOfCities1; city1++){
        if (hasStation[city1] == true){
            maxDist1 = max((dist1 + 1) / 2, maxDist1);
            dist1 = 0;
        }
        else
            dist1 += 1;
    }
    return max(maxDist1, dist1);
}

// ドライバーコード
int main(){
    int numOfCities1 = 6;
    int station1[] = {2, 4};
    int N = sizeof(station1) / sizeof(station1[0]);
    cout << "Max Distance:" << findMaxDistance(numOfCities1,
    station1, N);
}

実行結果

Max Distance:2