สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ มีเครื่องบิน n ลำบนโลก หมายเลข 1 ถึง n เครื่องบินหมายเลข i ชอบเครื่องบิน A[i] A[i] != i เราต้องตรวจสอบว่ามีเครื่องบิน 3 ลำคือ p, q, และ r ที่ p ชอบ q, q ชอบ r และ r ชอบ p หรือไม่
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [2, 4, 5, 1, 3] ผลลัพธ์จะได้ True เพราะ triplet คือ [2, 4, 1]
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
n := ขนาดของ A สำหรับ i := 0 เมื่อ i < n เพิ่ม i ทีละ 1 ทำ: ถ้า A[A[A[i + 1]]] เท่ากับ i + 1 แล้ว: คืนค่า true คืนค่า false
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#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; }
ข้อมูลนำเข้า
{ 2, 4, 5, 1, 3 }
ข้อมูลส่งออก
1
