컨셉
0에서 N-1까지 번호가 매겨진 주어진 도시 수 N과 역이 위치한 도시와 관련하여 우리의 임무는 도시와 가장 가까운 역 사이의 최대 거리를 결정하는 것입니다. 역이 있는 도시는 임의의 순서로 제공될 수 있습니다.
입력
numOfCities = 6, stations = [2, 4]
출력
2
입력
numOfCities = 6, stations = [4]
출력
4
-
다음 그림은 6개 도시와 역이 녹색으로 강조 표시된 도시를 포함하는 첫 번째 예를 나타냅니다. 따라서 이 경우 가장 가까운 역에서 가장 먼 도시는 2의 거리에서 0입니다. 따라서 최대 거리는 1입니다.
-
두 번째 예에서 가장 가까운 역에서 가장 먼 도시는 0이고 거리가 4입니다. 따라서 최대 거리는 4입니다.
방법
여기 이 문제에 세 가지 가능한 경우가 있습니다. -
-
첫 번째 경우는 가장 먼 도시가 두 역 사이에 있을 때를 나타냅니다.
-
두 번째 경우는 가장 먼 도시가 첫 번째 역의 왼쪽에 있을 때를 나타냅니다.
-
마지막 경우는 가장 먼 도시가 마지막 역의 오른쪽에 있을 때를 나타냅니다.
위의 문제를 해결하기 위해 다음과 같은 알고리즘이 구현되었습니다 -
-
False를 사용하여 크기가 N(도시 수)인 부울 배열을 초기화합니다. 그런 다음 역이 있는 도시의 값을 True로 표시합니다.
-
다음으로 변수 dist를 0으로 초기화합니다. 첫 번째 city와 동일한 값으로 다른 variablemaxDist를 초기화해야 합니다(두 번째 경우에 사용).
-
모든 도시를 하나씩 순회하기 시작합니다.
-
현재 도시에 스테이션이 있는 경우 최대(dist+1)//2 및 maxDist를 maxDist에 할당하는 것으로 관찰되었습니다(첫 번째 경우에 사용됨). 또한 dist에 0을 할당합니다.
-
그렇지 않으면 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