โปรแกรม C++ หาดัชนีทหารที่สามารถสร้างหน่วยลาดตระเวนได้

สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n มีทหาร n นายยืนเป็นวงกลม สำหรับทหาร ความสูงคือ 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