資料結構
網路
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 次瀏覽
廣告