โจทย์: สถานีรถไฟฟ้า n สถานีวงกลม ระยะห่างระหว่างสถานีติดกันในอาร์เรย์ D D[i] = ระยะ i ถึง i+1, D[n-1] = ระยะ n-1 ถึง 0 หาระยะทางสั้นที่สุดจาก s ถึง t
Input: s=1, t=3, D=[2,3,4,9] → Output: 5 (ทางเข็มนาฬิกา: 3+4=7 ทางตรงข้าม: 2+9=11 → เลือก 5? ตรวจสอบ: s=1,t=3 คือ สถานี 1 ถึง 3 ระยะ D[1]+D[2]=3+4=7 ทางย้อน: D[3]+D[0]=9+2=11 แต่ output บอก 5... อาจเป็น index 0-based) → Output: 5
ขั้นตอนแก้
arr[1..n] := D sum1 := sum(arr) if s > t: swap(s,t) sum2 := sum(arr[s..t-1]) return min(sum2, 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, t=3;
vector<int> D = {2,3,4,9};
cout << solve(s,t,D) << endl;
}Input
1, 3, {2,3,4,9}Output
5
