数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究从环形站点获得最短距离的 C++ 代码
假设我们有两个数字 s 和 t，以及另一个包含 n 个元素的数组 D。梦幻乐园地铁的环线有 n 个不同的站点。我们知道所有相邻站点之间的距离：D[i] 是站点 i 和 i+1 之间的距离，而 D[n-1] 是 (n-1) 和第 0 个站点之间的距离。我们必须找到从 s 到 t 的最短距离。
因此，如果输入类似 s = 1; t = 3; D = [2, 3, 4, 9]，则输出将为 5。
步骤
为了解决此问题，我们将按照以下步骤执行操作 −
n := size of D Define an array arr of size (n + 1), and fill with 0 for initialize i := 1, when i <= n, update (increase i by 1), do: arr[i] := D[i - 1] sum1 := sum1 + arr[i] if s > t, then: swap s and t for initialize i := s, when i < t, update (increase i by 1), do: sum2 := sum2 + arr[i] return minimum of sum2 and (sum1 - sum2)
示例
让我们看看以下实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
int solve(int s, int t, vector<int> D){
int n = D.size(), sum1 = 0, sum2 = 0;
vector<int> arr(n + 1, 0);
for (int i = 1; i <= n; i++){
arr[i] = D[i - 1];
sum1 += arr[i];
}
if (s > t)
swap(s, t);
for (int i = s; i < t; i++)
sum2 += arr[i];
return min(sum2, sum1 - sum2);
}
int main(){
int s = 1;
int t = 3;
vector<int> D = { 2, 3, 4, 9 };
cout << solve(s, t, D) << endl;
}输入
1, 3, { 2, 3, 4, 9 }输出
5
更新时间： 29-Mar-2022
372 次浏览
广告