Giả sử chúng ta có một mảng A với n phần tử. Có n binh sĩ đứng trên một vòng tròn. Đối với binh sĩ thứ i, chiều cao là A[i]. Một đơn vị trinh sát có thể được tạo từ hai binh sĩ liền kề, sự khác biệt chiều cao của họ là tối thiểu. Vì vậy, mỗi người sẽ ít được nhận ra hơn với người kia. Chúng ta phải tìm chỉ số của cặp binh sĩ có thể tạo đơn vị trinh sát.
Ví dụ, nếu đầu vào là A = [10, 12, 13, 15, 10], thì đầu ra sẽ là (5, 1).
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
n := kích thước của A D := |A[0] - A[n - 1]| H := n for khởi tạo i := 1, khi i < n, cập nhật (tăng i lên 1), do: if D > |A[i] - A[i - 1]|, thì: D := |A[i] - A[i - 1]| H := i in H và (H mod n)
Ví dụ
Xem triển khai sau để hiểu rõ hơ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); }Đầu vào
{ 10, 12, 13, 15, 10 }Đầu ra
5, 1