Giả sử chúng ta có một mảng A với n phần tử. Có n máy bay trên Trái Đất và chúng được đánh số từ 1 đến n. Máy bay số i thích máy bay A[i]. A[i] != i. Chúng ta phải kiểm tra xem có ba máy bay p, q, và r nào mà p thích q, q thích r và r thích p hay không.
Ví dụ, nếu đầu vào là A = [2, 4, 5, 1, 3], thì đầu ra sẽ là True, vì bộ ba là [2, 4, 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 for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), do: if A[A[A[i + 1]]] giống i + 1, thì: return true return false
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; bool solve(vector<int> A) { int n = A.size(); for (int i = 0; i < n; i++) { if (A[A[A[i + 1]]] == i + 1) { return true; } } return false; } int main() { vector<int> A = { 2, 4, 5, 1, 3 }; cout << solve(A) << endl; }Đầu vào
{ 2, 4, 5, 1, 3 }Đầu ra
1