C++-এ শহর এবং স্টেশনের মধ্যে সর্বোচ্চ দূরত্ব নির্ণয়

কনসেপ্ট

N সংখ্যক শহর (০ থেকে N-1 নম্বরিং) এবং স্টেশন থাকা শহরগুলো দেওয়া আছে। যেকোনো শহর থেকে তার নিকটতম স্টেশনের মধ্যে সর্বোচ্চ দূরত্ব নির্ণয় করুন। স্টেশন থাকা শহরগুলো যেকোনো ক্রমে দেওয়া হতে পারে।

ইনপুট ১

numOfCities = 6, stations = [2, 4]

আউটপুট ১

2

ইনপুট ২

numOfCities = 6, stations = [4]

আউটপুট ২

4

পদ্ধতি

তিনটি সম্ভাব্য কেস:

• সর্বোচ্চ দূরত্বের শহর দুইটি স্টেশনের মাঝপথে।
• প্রথম স্টেশনের বামপাশে।
• শেষ স্টেশনের ডানপাশে।

অ্যালগরিদম: ১) বুলিয়ান অ্যারে দিয়ে স্টেশন থাকা শহরগুলো মার্ক করুন। ২) dist = 0, maxDist = প্রথম স্টেশনের ইনডেক্স (দ্বিতীয় কেসের জন্য)। ৩) সব শহর দিয়ে লুপ করুন। যদি স্টেশন পাওয়া যায়, maxDist = max((dist+1)/2, maxDist) এবং dist = 0। নয়লে dist++। ৪) অবশেষে max(maxDist, dist) ফেরত দিন (তৃতীয় কেসের জন্য)।

উদাহরণ (C++ কোড)

// C++ প্রোগ্রাম: যেকোনো শহর থেকে নিকটতম স্টেশনের সর্বোচ্চ দূরত্ব
#include <bits/stdc++.h>
using namespace std;

int findMaxDistance(int numOfCities1, int station1[], int N) {
    bool hasStation[numOfCities1 + 1] = {false};
    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 << "সর্বোচ্চ দূরত্ব: " << findMaxDistance(numOfCities1, station1, N);
    return 0;
}

আউটপুট

সর্বোচ্চ দূরত্ব: 2