Tìm khoảng cách lớn nhất giữa thành phố và trạm gần nhất trong C++

Khái niệm

Cho số thành phố N được đánh số từ 0 đến N-1 và các thành phố có trạm, nhiệm vụ là xác định khoảng cách lớn nhất giữa bất kỳ thành phố nào và trạm gần nhất của nó. Các thành phố có trạm có thể cho 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 sau minh họa ví dụ đầu tiên với 6 thành phố và các thành phố có trạm được tô màu xanh. Thành phố xa trạm nhất là 0 với khoảng cách 2. Do đó khoảng cách lớn nhất là 2.

• Trong ví dụ thứ hai, thành phố xa trạm nhất là 0 với khoảng cách 4. Do đó khoảng cách lớn nhất là 4.

Phương pháp

Có ba trường hợp có thể xảy ra:

• Trường hợp 1: Thành phố xa nhất nằm giữa hai trạm.
• Trường hợp 2: Thành phố xa nhất nằm bên trái trạm đầu tiên.
• Trường hợp 3: Thành phố xa nhất nằm bên phải trạm cuối cùng.

Thuật toán:

• Khởi tạo mảng boolean kích thước N (số thành phố) với False. Đánh dấu các thành phố có trạm là True.
• Khởi tạo biến dist = 0. Khởi tạo biến maxDist bằng thành phố đầu tiên có trạm (dùng cho trường hợp 2).
• Duyệt qua tất cả các thành phố một by one.
• Nếu thành phố hiện tại có trạm, gán maxDist = max((dist+1)//2, maxDist) (dùng cho trường hợp 1). Gán dist = 0.
• Ngược lại, tăng dist lên 1.
• Cuối cùng, trả về max(maxDist, dist) (dùng cho trường hợp 3).

Ví dụ

// Chương trình C++ tính khoảng cách lớn nhất giữa thành phố và trạm gần nhất
#include<bits/stdc++.h>
using namespace std;

// Hàm tính khoảng cách lớn nhất
int findMaxDistance(int numOfCities1,int station1[],int N){
    // Khởi tạo mảng boolean
    bool hasStation[numOfCities1 + 1] = {false};
    // Đánh dấu thành phố có trạm là 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);
}

// Chương trình chính
int main(){
    int numOfCities1 = 6;
    int station1[] = {2,4};
    int N = sizeof(station1)/sizeof(station1[0]);
    cout << "Khoảng cách tối đa: " << findMaxDistance(numOfCities1, station1, N);
}

Đầu ra

Khoảng cách tối đa:2