โปรแกรม C++ เพื่อค้นหาขนาดของอาร์เรย์ที่ลดลงหลังจากการลบออก

สมมติว่าเรามีอาร์เรย์ 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