Cho biến nguyên Number làm đầu vào. Xét mảng chứa các phần tử từ 1 đến Number theo thứ tự bất kỳ. Thực hiện phép toán Number-1 lần trên mảng:
Chọn hai phần tử A và B từ mảng.
Loại bỏ A và B khỏi mảng.
Thêm tổng bình phương của A và B vào mảng.
Cuối cùng sẽ được một giá trị nguyên đơn; mục tiêu là tìm giá trị lớn nhất có thể cho phần tử đó.
Sử dụng hàng đợi ưu tiên (Priority Queue)
Để tối đa hóa kết quả cuối, phải chọn A, B lớn nhất.
Dùng priority queue lưu giá trị các phần tử theo thứ tự giảm dần.
Phần tử đầu hàng đợi là lớn nhất. Lấy hai phần tử đầu, đẩy bình phương tổng chúng vào hàng đợi lại.
Lặp Number - 1 lần để lấy kết quả.
Ví dụ
Đầu vào - Number = 2
Đầu ra - Phần tử đơn sau giảm mảng: 5
Giải thích - Mảng [1, 2]. Priority Queue: 2, 1. A=2, B=1: A²+B²=4+1=5. Phần tử cuối: 5.
Đầu vào - Number = 5
Đầu ra - Phần tử đơn sau giảm mảng: 1187163713
Giải thích - Mảng [5,1,2,4,3]. Priority Queue: 5,4,3,2,1. Các bước: 5²+4²=41 → 41,3,2,1; 41²+3²=1690 → 1690,2,1; 1690²+2²=2856104 → 2856104,1; 2856104²+1²=1187163713. Phần tử cuối: 1187163713.
Phương pháp sử dụng trong chương trình dưới đây
Dùng priority queue lưu các phần tử mảng theo thứ tự giảm dần. Lấy hai phần tử lớn nhất, đẩy tổng bình phương vào hàng đợi. Lặp cho đến khi chỉ còn một giá trị.
Nhập biến Number.
Kiểu dữ liệu kết quả: long long int (lli).
Hàm reduceArray(int Num) trả về số nguyên đơn lớn nhất.
Tạo priority_queue<lli> pQueue.
Điền pQueue bằng số 1 đến N bằng vòng lặp while.
Duyệt pQueue while size >= 1: lấy var1 = top(), pop(); var2 = top(), pop(); var1=var1², var2=var2²; push(var1+var2).
Trả về top() cuối cùng.
In kết quả trong main.
Ví dụ mã
#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<<"Phần tử đơn sau giảm mảng: "<<reduceArray(Number); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Phần tử đơn sau giảm mảng: 1187163713