순환 스테이션에서 최단 거리를 구하는 C++ 코드

<시간/>

두 개의 숫자 s와 t가 있고 n개의 요소가 있는 또 다른 배열 D가 있다고 가정합니다. 드림랜드 지하철 순환선에는 n개의 역이 있습니다. 우리는 모든 인접 스테이션 쌍 사이의 거리를 알고 있습니다. D[i]는 스테이션 i와 i+1 사이의 거리이고 D[n-1]은 (n-1)과 0번째 스테이션 사이의 거리입니다. 에서 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 }