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

แนวคิด

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

อินพุต

numOfCities = 6, stations = [2, 4]

เอาต์พุต

2

อินพุต

numOfCities = 6, stations = [4]

เอาต์พุต

4

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

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

วิธีการ

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

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

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

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

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

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

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

• เริ่มลูปผ่านเมืองทั้งหมดทีละอัน

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

• มิฉะนั้น เพิ่ม dist ขึ้น 1

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

ตัวอย่างโค้ด

// โปรแกรม C++ เพื่อคำนวณระยะทางสูงสุด // ระหว่างเมืองใดๆ // และสถานีที่ใกล้ที่สุด #include<bits/stdc++.h> using namespace std; // ฟังก์ชันแสดงการคำนวณระยะทางสูงสุด // ระหว่างเมืองใดๆ และสถานีที่ใกล้ที่สุด int findMaxDistance(int numOfCities1,int station1[],int N){    // ใช้เริ่มต้น boolean list    bool hasStation[numOfCities1 + 1] = {false};    // ใช้กำหนด 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); } //โค้ดหลัก 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