C++で任意の都市と駅の間の最大距離を見つける

コンセプト

0からN-1までの番号が付けられたNの都市の数と、駅が配置されている都市に関して、私たちのタスクは、任意の都市とその最寄りの駅との間の最大距離を決定することです。駅のある都市は任意の順序で指定できることに注意してください。

入力

numOfCities = 6, stations = [2, 4]

出力

2

入力

numOfCities = 6, stations = [4]

出力

4

• 次の図は、6つの都市と、駅が緑色で強調表示されている都市を含む最初の例を示しています。したがって、この場合、最も近い駅からの最も遠い距離は2の距離で0です。したがって、最大距離は1です。

• 2番目の例では、最も近い駅から最も遠い都市は0であり、距離は4です。したがって、最大距離は4です。

メソッド

ここで、この問題には3つのケースが考えられます-

• 最初のケースは、最も遠い都市が2つの駅の間にあることを示しています。

• 2番目のケースは、最も遠い都市が最初の駅の左側にあることを示しています。

• 最後のケースは、最も遠い都市が最後の駅の右側にあることを示しています。

上記の問題を解決するために、次のアルゴリズムが実装されています-

• サイズN（都市の数）のブール配列をFalseで初期化します。その後、駅のある都市の値をTrueとしてマークします

• 次に、変数distを0で初期化します。別のvariablemaxDistを、ステーションのある最初の都市と同じ値で初期化する必要があります（2番目のケースで使用）。

• すべての都市を1つずつループし始めます。

• 現在の都市に駅がある場合は、最大値（dist + 1）// 2とmaxDistをmaxDistに割り当てます（最初のケースで使用）。さらに、distに0を割り当てます。

• それ以外の場合は、距離をインクリメントします。

• 最後に、distとmaxDistの最大値を返します（3番目のケースに使用されます）。

例

// C++ program to calculate the maximum
// distance between any city
// and its nearest station
#include<bits/stdc++.h>
using namespace std;
// Shows function to compute the maximum
// distance between any city and its nearest station
int findMaxDistance(int numOfCities1,int station1[],int N){
   // Used to initialize boolean list
   bool hasStation[numOfCities1 + 1] = {false};
   // Used to assign True to cities containing station
   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);
}
//Driver code
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