สมมติว่าเรามีตัวเลขสองตัว s และ t และอีกอาร์เรย์ D ที่มีองค์ประกอบ n รถไฟใต้ดินสายวงกลมของ Dreamland มีสถานีที่แตกต่างกัน n สถานี เราทราบระยะทางระหว่างสถานีใกล้เคียงทุกคู่:D[i] คือระยะห่างระหว่างสถานี i และ i+1 และ D[n-1] คือระยะห่างระหว่าง (n-1) และสถานีที่ 0 เราต้องหาระยะทางที่สั้นที่สุดจาก s ถึง t.
ดังนั้น ถ้าอินพุตเป็น s =1; เสื้อ =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
