สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบ พิจารณาว่ามีรหัสผ่าน n จำนวนเต็มบวก เราใช้การดำเนินการต่อไปนี้กับอาร์เรย์ การดำเนินการคือ ลบสององค์ประกอบที่ติดกันซึ่งไม่เท่ากัน แล้ววางผลรวมของพวกมันที่ตำแหน่งนั้น การดำเนินการนี้จะลดขนาดอาร์เรย์ลง 1 เราต้องหาความยาวสั้นที่สุดของอาร์เรย์หลังจากดำเนินการเหล่านี้
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [2, 1, 3, 1] ผลลัพธ์จะได้ 1 เพราะถ้าเลือก (1, 3) อาร์เรย์จะเป็น [2, 4, 1] แล้วเลือก (2, 4) ทำให้เป็น [6, 1] แล้วเลือกคู่สุดท้ายได้ [7]
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
n := ขนาดของ A กำหนดเซต se สำหรับ i := 0 เมื่อ i < n เพิ่ม i ทีละ 1 ทำ: แทรก A[i] ลงใน se ถ้าขนาดของ se เท่ากับ 1 แล้ว: คืนค่า n มิฉะนั้น คืนค่า 1
ตัวอย่างโค้ด
ดูการนำไปใช้จริงด้านล่างเพื่อความเข้าใจที่ดียิ่งขึ้น:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A) { int n = A.size(); set<int> a; for (int i = 0; i < n; i++) { a.insert(A[i]); } if (a.size() == 1) return n; else return 1; } int main() { vector<int> A = { 2, 1, 3, 1 }; cout << solve(A) << endl; }
ข้อมูลนำเข้า
{ 2, 1, 3, 1 }
ข้อมูลส่งออก
1
