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

ภาพรวม

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

• เลือกสองอิลิเมนต์ A และ B จากอาร์เรย์
• นำ A และ B ออกจากอาร์เรย์
• เพิ่มผลรวมของกำลังสองของ A และ B (A² + B²) กลับเข้าไปในอาร์เรย์

สุดท้ายจะเหลือจำนวนเต็มเพียงตัวเดียว เป้าหมายคือหาค่าสูงสุดที่เป็นไปได้ของตัวเลขตัวสุดท้ายนั้น

ใช้ Priority Queue

• เพื่อให้ได้ผลลัพธ์สูงสุด ต้องเลือก A และ B ให้มากที่สุด
• ใช้ Priority Queue เก็บค่าอิลิเมนต์ เรียงจากมากไปน้อย
• อิลิเมนต์บนสุด (Top) จะมีค่ามากที่สุด ดังนั้นจึง Pop สองตัวบนสุด นำกำลังสองมาบวกกัน Push กลับเข้า Queue
• ทำซ้ำ Number-1 ครั้ง จนเหลือค่าเดียว

ตัวอย่าง

อินพุต − Number = 2

เอาต์พุต − Single element after array reduction: 5

คำอธิบาย − อาร์เรย์ [1, 2] → Priority Queue: 2, 1 → A=2, B=1 → 2²+1²=4+1=5 → เหลือ 5

อินพุต − Number = 5

เอาต์พุต − Single element after array reduction: 1187163713

คำอธิบาย − อาร์เรย์ [5,1,2,4,3] → PQ: 5,4,3,2,1 → 5²+4²=41 → 41,3,2,1 → 41²+3²=1690 → 1690,2,1 → 1690²+2²=2856104 → 2856104,1 → 2856104²+1²=1187163713

แนวทางการแก้ปัญหา

ใช้ Priority Queue เก็บอิลิเมนต์ 1 ถึง N เรียงมากไปน้อย Pop สองตัวบนสุด นำกำลังสองมาบวก Push กลับ ทำซ้ำจนเหลือค่าเดียว

• รับตัวแปร Number
• ใช้ long long int (typedef lli) สำหรับผลลัพธ์
• ฟังก์ชัน reduceArray(int Num) คืนค่าจำนวนเต็มสูงสุด
• สร้าง priority_queue<lli> pQueue
• เติม PQ ด้วยเลข 1 ถึง N ด้วย while loop
• วน while pQueue.size() > 1
• Pop สองตัวบนสุด var1, var2
• คำนวณ var1*var1 + var2*var2 Push กลับ
• คืนค่า pQueue.top()
• พิมพ์ผลลัพธ์ใน main

ตัวอย่างโค้ด C++

#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