資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢任意城市和車站之間的最大距離
概念
關於給定的城市數量 N（從 0 到 N-1 編號）和設有車站的城市，我們的任務是確定任意城市與其最近車站之間的最大距離。需要注意的是，設有車站的城市可以以任意順序給出。
輸入
numOfCities = 6, stations = [2, 4]
輸出
2
輸入
numOfCities = 6, stations = [4]
輸出
4
下圖顯示了第一個示例，其中包含 6 個城市，並且設有車站的城市以綠色突出顯示。因此，在這種情況下，距離其最近車站最遠的城市是 0，距離為 2。因此最大距離為 1。
在第二個示例中，距離其最近車站最遠的城市是 0，距離為 4。因此最大距離為 4。
方法
這裡，此問題中存在三種可能的情況：
第一種情況表示最遠城市位於兩個車站之間。
第二種情況表示最遠城市位於第一個車站的左側。
最後一種情況表示最遠城市位於最後一個車站的右側。
為了解決上述問題，實現了以下演算法：
我們初始化一個大小為 N（城市數量）的布林陣列，其值為 False。然後將設有車站的城市的相應值標記為 True。
接下來，我們將變數 dist 初始化為 0。我們必須初始化另一個變數 maxDist，其值為第一個設有車站的城市的值（用於第二種情況）。
開始逐個遍歷所有城市。
已經觀察到，如果當前城市設有車站，則將 (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
更新於： 2020年7月25日
371 次瀏覽
廣告