ลดอาร์เรย์เป็นจำนวนเต็มเดียวด้วยการดำเนินการที่กำหนดใน C++

กำหนดตัวแปรจำนวนเต็ม Number เป็นอินพุต ให้เราพิจารณาอาร์เรย์ที่มีองค์ประกอบในช่วง 1 ถึง Number ในลำดับใดก็ได้ หากเราทำการดำเนินการ Number-1 ครั้งในอาร์เรย์ดังกล่าว

• เราเลือกสององค์ประกอบ A และ B จากอาร์เรย์

• ลบ A และ B ออกจากอาร์เรย์

• เพิ่มผลรวมของกำลังสองของ A และ B ให้กับอาร์เรย์

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

การใช้คิวลำดับความสำคัญ

• เพื่อให้ได้ผลลัพธ์สูงสุด เราจะต้องเลือก A และ B ให้ได้มากที่สุด

• ในการหาค่า A และ B สูงสุด เราจะใช้ลำดับความสำคัญของคิวเพื่อเก็บค่าขององค์ประกอบไว้ข้างใน

• คิวลำดับความสำคัญเก็บองค์ประกอบในลำดับที่ลดลง

• องค์ประกอบบนสุดมีค่ามากที่สุดเป็นต้น ดังนั้นหลังจากเปิดสององค์ประกอบแล้ว เราจะผลักสี่เหลี่ยมของพวกมันไปที่คิวอีกครั้ง

• จะปรากฏขึ้นและกดหมายเลข - 1 ครั้งเพื่อให้ได้ผลลัพธ์ที่ต้องการ

ตัวอย่าง

ป้อนข้อมูล − Number=2

ผลผลิต − องค์ประกอบเดี่ยวหลังการลดอาร์เรย์:5

คำอธิบาย − สมมติว่าเรามีองค์ประกอบในอาร์เรย์เป็น [ 1 2]

หลังจากใส่ Priority Queue-:2 1

A=5, B=4 :A ² +B ² =1+4=5

Last element:5

ป้อนข้อมูล − Number=5

ผลผลิต − องค์ประกอบเดี่ยวหลังการลดอาร์เรย์:5

คำอธิบาย − สมมติว่าเรามีองค์ประกอบในอาร์เรย์เป็น [ 5 1 2 4 3]

หลังจากใส่ Priority Queue-:5 4 3 2 1

A=5, B=4 :A ² +B ² =25+16=41 :41 3 2 1

A=41, B=3 :A ² +B ² =1681+9=1690 :1690 2 1

A=1690, B=2 :A ² +B ² =1681+4=2856104 :2856104 1

A=2856104 , B=1 :A ² +B ² =1187163712+1=1187163713 :1187163713

Last element :1187163713

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราจะจัดลำดับความสำคัญของคิวเพื่อจัดเก็บองค์ประกอบของอาร์เรย์ในลำดับที่ลดลง ป๊อปอัพสององค์ประกอบที่ยิ่งใหญ่ที่สุดและผลักผลรวมของสี่เหลี่ยมทั้งสองไปที่คิวนั้นอีกครั้ง ทำเช่นนี้จนเหลือเพียงค่าเดียวเท่านั้น

• นำตัวแปรอินพุต Number.

• ใช้ประเภทข้อมูลสำหรับผลลัพธ์เป็นจำนวนเต็มยาว - lli

• ฟังก์ชัน reduceArray(int Num) รับหมายเลขอินพุตและส่งกลับจำนวนเต็มสูงสุดเดียวที่คำนวณโดยใช้การดำเนินการข้างต้น

• รับลำดับความสำคัญของคิวเป็น pQueue

• เติม pQueue ด้วยตัวเลข 1 ถึง N โดยใช้ลูป while

• ขณะที่ i<=Num ให้กด i ไปที่ pQueue

• ตอนนี้ pQueue มีจำนวนเต็ม 1 ถึง N โดยลดลงและขนาดเป็น N

• ตอนนี้สำรวจ pQueue โดยใช้ while loop จนถึงขนาด>=1

• ใช้ค่าสูงสุดเป็น var1=pQueue.top() และเปิดมันขึ้นมา

• ใช้ค่าสูงสุดถัดไปเป็น var2=pQueue.top() แล้วป๊อปอัป

• ตั้งค่า var1 เป็นสี่เหลี่ยมจัตุรัส และ var2 เป็นสี่เหลี่ยมจัตุรัส

• กด var1+var2 ไปที่ pQueue อีกครั้ง

• ที่ส่วนท้ายของลูป while ให้คืนค่าองค์ประกอบด้านบน

• พิมพ์ผลลัพธ์ภายใน main.

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int reduceArray(int Num){
   priority_queue<lli> pQueue;
   int i=1;
   while(i<=Num){
      pQueue.push(i);
      i=i+1;
   }
   while (pQueue.size() > 1) {
      lli var1 = pQueue.top();
      pQueue.pop();
      lli var2 = pQueue.top();
      pQueue.pop();
      var1=var1*var1;
      var2=var2*var2;
      pQueue.push(var1+var2);
   }
   return pQueue.top();
}
int main(){
   int Number = 5;
   cout<<"Single element after array reduction: "<<reduceArray(Number);
   return 0;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

Single element after array reduction: 1187163713