สมมติว่าเรามีอาร์เรย์ A ที่มีองค์ประกอบ n พิจารณาว่ามีรหัสผ่านที่มีจำนวนเต็มบวก n เราใช้การดำเนินการต่อไปนี้กับอาร์เรย์ การดำเนินการคือการลบสององค์ประกอบที่อยู่ติดกันซึ่งไม่เหมือนกัน จากนั้นใส่ผลรวมที่ตำแหน่งนั้น ดังนั้นการดำเนินการนี้จะลดขนาดของอาร์เรย์ลง 1 เราต้องหาความยาวของอาร์เรย์ที่สั้นที่สุดหลังจากดำเนินการเหล่านี้
ดังนั้นหากอินพุตเป็น A =[2, 1, 3, 1] ผลลัพธ์จะเป็น 1 เพราะหากเราเลือก (1, 3) อาร์เรย์จะเป็น [2, 4, 1] แล้วเลือก (2, 4) เพื่อสร้างอาร์เรย์ [6, 1] จากนั้นเลือกสองตัวสุดท้ายเพื่อรับ [7]
ขั้นตอน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
n := size of A Define one set se for initialize i := 0, when i < n, update (increase i by 1), do: insert A[i] into se if size of se is same as 1, then: return n Otherwise return 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
