สร้างอาร์เรย์เป้าหมายด้วยผลรวมหลายรายการใน C++

สมมติว่าเรามีเป้าหมายอาร์เรย์ของจำนวนเต็ม จากอาร์เรย์เริ่มต้น A ที่ประกอบด้วย 1 ทั้งหมด เราสามารถดำเนินการตามขั้นตอนต่อไปนี้ -

• ให้ถือว่า x คือผลรวมขององค์ประกอบทั้งหมดที่อยู่ในอาร์เรย์ของเราในปัจจุบัน

• เลือกดัชนี i ในช่วง 0 ถึง n โดยที่ n คือขนาดของอาร์เรย์และตั้งค่าของ A ที่ดัชนี i ถึง x

• เราสามารถทำซ้ำขั้นตอนนี้ได้หลายครั้งตามต้องการ

เราต้องตรวจสอบว่าเป็นไปได้ไหมที่จะสร้างอาร์เรย์เป้าหมายจาก A มิฉะนั้นจะคืนค่าเป็นเท็จ

ดังนั้นหากอินพุตเป็น [3,9,5] เอาต์พุตจะเป็น True เนื่องจากเราสามารถเริ่มต้นด้วยดัชนี [1,1,1] ผลรวมคือ 3 ที่ดัชนี 0 ดังนั้นอาร์เรย์จะเป็น [3 ,1,1] ผลรวมคือ 5 ที่ดัชนี 2 จากนั้นอาร์เรย์คือ [3,1,5] ผลรวมคือ 9 ที่ดัชนี 1 ดังนั้นอาร์เรย์คือ [3,9,5]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ผลรวม :=0

• n :=ขนาดของเป้าหมาย

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ผลรวม :=ผลรวม + เป้าหมาย[i]

• กำหนดลำดับความสำคัญของคิว pq และเริ่มต้นด้วยอาร์เรย์เป้าหมาย

• ในขณะที่องค์ประกอบด้านบนของ pq> ผลรวม ทำ -

  • x :=องค์ประกอบด้านบนของ pq

  • ลบองค์ประกอบออกจาก pq

  • แทรก 2 * x - ผลรวมเป็น pq

  • ผลรวม :=x

• คืนค่า จริง เมื่อผลรวมเท่ากับขนาดของเป้าหมาย มิฉะนั้น เท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   bool isPossible(vector<int>& target) {
      lli sum = 0;
      int n = target.size();
      for (int i = 0; i < n; i++) {
         sum += target[i];
      }
      priority_queue<int> pq(target.begin(), target.end());
      while (pq.top() * 2 > sum) {
         int x = pq.top();
         pq.pop();
         pq.push(2 * x - sum);
         sum = x;
      }
      return sum == (int)target.size();
   }
};
main(){
   Solution ob;
   vector<int> v = {3,9,5};
   cout << (ob.isPossible(v));
}

อินพุต

{3,9,5}

ผลลัพธ์

1