정찰부대를 구성할 수 있는 병사들의 지수를 찾는 C++ 프로그램

n개의 요소가 있는 배열 A가 있다고 가정합니다. 원 위에 n명의 병사가 서 있다. i번째 병사의 경우 키는 A[i]입니다. 정찰 부대는 높이 차이가 최소인 인접한 두 병사로 만들 수 있습니다. 그래서 그들 각각은 서로 덜 눈에 띄게 될 것입니다. 정찰부대를 구성할 수 있는 병사 쌍의 인덱스를 찾아야 합니다.

따라서 입력이 A =[10, 12, 13, 15, 10]과 같으면 출력은 (5, 1)이 됩니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of A
D := |A[0] - A[n - 1]|
H := n
for initialize i := 1, when i < n, update (increase i by 1), do:
   if D > |A[i] - A[i - 1]|, then:
      D := |A[i] - A[i - 1]|
      H := i
print H and (H mod n)

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A) {
   int n = A.size();
   int D = abs(A[0] - A[n - 1]);
   int H = n;
   for (int i = 1; i < n; i++) {
      if (D > abs(A[i] - A[i - 1])) {
         D = abs(A[i] - A[i - 1]);
         H = i;
      }
   }
   cout << H << ", " << (H % n) + 1;
}
int main() {
   vector<int> A = { 10, 12, 13, 15, 10 };
   solve(A);
}

입력

{ 10, 12, 13, 15, 10 }

출력

5, 1