मान लीजिए हमारे पास दो संख्याएं 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