ค้นหาระยะทางสูงสุดระหว่างเมืองและสถานีใด ๆ ใน C++

แนวคิด

สำหรับจำนวนเมืองที่กำหนด N ที่มีหมายเลขตั้งแต่ 0 ถึง N-1 และเมืองที่สถานีตั้งอยู่ หน้าที่ของเราคือกำหนดระยะทางสูงสุดระหว่างเมืองใดๆ และสถานีที่ใกล้ที่สุด ควรสังเกตว่าสามารถกำหนดเมืองที่มีสถานีในลำดับใดก็ได้

อินพุต

numOfCities = 6, stations = [2, 4]

ผลลัพธ์

2

อินพุต

numOfCities = 6, stations = [4]

ผลลัพธ์

4

• รูปต่อไปนี้แสดงถึงตัวอย่างแรกที่มี 6 เมืองและเมืองที่มีสถานีที่เน้นด้วยสีเขียว ดังนั้น ในกรณีนี้ เมืองที่ไกลที่สุดจากสถานีที่ใกล้ที่สุดคือ 0 ที่ระยะห่าง 2 ดังนั้น ระยะทางสูงสุดคือ 1

• ในตัวอย่างที่สอง เมืองที่ไกลที่สุดจากสถานีที่ใกล้ที่สุดคือ 0 ซึ่งเป็นระยะทาง 4 ดังนั้นระยะทางสูงสุดคือ 4

วิธีการ

มีสามกรณีที่เป็นไปได้ในปัญหานี้ -

• กรณีแรกระบุว่าเมืองที่ไกลที่สุดอยู่ระหว่างสองสถานี

• กรณีที่สองระบุว่าเมืองที่ไกลที่สุดจะอยู่ทางด้านซ้ายของสถานีแรกเมื่อใด

• กรณีสุดท้ายระบุว่าเมืองที่ไกลที่สุดอยู่ทางด้านขวาของสถานีสุดท้ายเมื่อใด

อัลกอริทึมต่อไปนี้ถูกนำมาใช้เพื่อแก้ปัญหาข้างต้น -

• เราเริ่มต้นอาร์เรย์บูลีนขนาด N (จำนวนเมือง) ด้วย "เท็จ" หลังจากนั้นให้ทำเครื่องหมายค่าของเมืองด้วยสถานีเป็น True

• ต่อไปเราจะเริ่มต้นตัวแปร dist ด้วย 0 เราต้องเริ่มต้นตัวแปรอื่น maxDist ที่มีค่าซึ่งเหมือนกับเมืองแรกที่มีสถานี (ใช้สำหรับกรณีที่สอง)

• เริ่มวนรอบเมืองทั้งหมดทีละเมือง

• มีการสังเกตว่าถ้าเมืองปัจจุบันมีสถานีแล้วกำหนดสูงสุดของ (dist+1)//2 และ maxDist ให้กับ maxDist (ใช้สำหรับกรณีแรก) นอกจากนี้ กำหนด 0 ให้กับ dist.

• มิฉะนั้น เพิ่ม dist.

• สุดท้าย คืนค่าสูงสุดของ dist และ maxDist (ใช้สำหรับกรณีที่สาม)

ตัวอย่าง

// 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