สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ มีทหาร n คนยืนวงกลม สำหรับทหารคนที่ i ความสูงคือ A[i] หน่วยลาดตระเวน (reconnaissance unit) สามารถจัดได้จากสองทหารที่ติดกัน ซึ่งความต่างของความสูงน้อยที่สุด ดังนั้นแต่ละคนจะไม่เด่นชัดกับอีกคน เราต้องหาดัชนีของคู่ทหารที่สามารถจัดเป็นหน่วยลาดตระเวนได้
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [10, 12, 13, 15, 10] ผลลัพธ์จะได้ (5, 1)
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
n := ขนาดของ A D := |A[0] - A[n - 1]| H := n สำหรับ i := 1 เมื่อ i < n เพิ่ม i ทีละ 1 ทำ: ถ้า D > |A[i] - A[i - 1]| แล้ว: D := |A[i] - A[i - 1]| H := i พิมพ์ H และ (H mod n) + 1
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#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
