Tìm khoảng cách tối đa giữa bất kỳ thành phố và nhà ga nào trong C ++

Khái niệm

Đối với số lượng thành phố N được đánh số từ 0 đến N-1 và các thành phố có ga, nhiệm vụ của chúng tôi là xác định khoảng cách tối đa giữa bất kỳ thành phố nào và ga gần nhất của nó. Cần lưu ý rằng các thành phố có nhà ga có thể được cung cấp theo bất kỳ thứ tự nào.

Đầu vào

numOfCities = 6, stations = [2, 4]

Đầu ra

2

Đầu vào

numOfCities = 6, stations = [4]

Đầu ra

4

• Hình dưới đây chỉ ra ví dụ đầu tiên chứa 6 thành phố và các thành phố có các ga được đánh dấu bằng màu xanh lá cây. Vì vậy, trong trường hợp này, khoảng cách xa nhất từ ​​các điểm gần nhất của nó là 0 ở khoảng cách 2. Do đó khoảng cách tối đa là 1.

• Trong ví dụ thứ hai, thành phố xa nhất từ ​​ga gần nhất của nó là 0 với khoảng cách là 4. Do đó khoảng cách tối đa là 4.

Phương pháp

Ở đây, có ba trường hợp có thể xảy ra trong vấn đề này -

• Trường hợp đầu tiên cho biết khi thành phố xa nhất nằm giữa hai nhà ga.

• Trường hợp thứ hai cho biết khi thành phố xa nhất nằm ở bên trái của nhà ga đầu tiên.

• Chữ hoa cuối cho biết khi thành phố xa nhất nằm ở phía bên phải của nhà ga cuối cùng.

Thuật toán sau được thực hiện để giải quyết vấn đề trên -

• Chúng tôi khởi tạo một mảng boolean có kích thước N (số thành phố) với False. Sau đó, đánh dấu giá trị của các thành phố có trạm là Đúng

• Tiếp theo, chúng ta khởi tạo một biến dist bằng 0. Chúng ta phải khởi tạo một biếnmaxDist khác có giá trị giống với thành phố đầu tiên có trạm (được sử dụng cho trường hợp thứ hai).

• Bắt đầu đi vòng qua tất cả các thành phố ony từng cái một.

• Người ta đã quan sát thấy rằng nếu thành phố hiện tại có một nhà ga, và sau đó gán giá trị tối đa (dist + 1) // 2 và maxDist cho maxDist (được sử dụng cho trường hợp đầu tiên). Ngoài ra, gán 0 cho dist.

• Khác, phiên bản tăng dần

• Cuối cùng, trả về giá trị tối đa của dist và maxDist (được sử dụng cho trường hợp thứ ba).

Ví dụ

// 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);
}

Đầu ra

Max Distance:2