数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告