หาจำนวนเต็มบวก N ตัวที่สอดคล้องสมการด้วย C++

ภาพรวมปัญหา

ได้รับ A, B, N หา N จำนวนเต็มบวก x₁...xₙ ที่:

x₁² + x₂² + ... + xₙ² ≥ A
x₁ + x₂ + ... + xₙ ≤ B


ตัวอย่าง
อินพุต
N = 4, A = 65, B = 16
เอาต์พุต
1 1 1 8
คำอธิบาย
1²+1²+1²+8² = 67 ≥ 65
1+1+1+8 = 11 ≤ 16

วิธีแก้ปัญหา
กลยุทธ์: ทำให้ผลรวมกำลังสองมากที่สุด โดยตั้ง N-1 ตัวเป็น 1 และตัวสุดท้ายเป็น B-(N-1)
เพราะ (x+1)² + (y-1)² > x² + y² เมื่อ x ≥ y (ทำให้กระจายมากขึ้น ผลรวมกำลังสองมากขึ้น)

โค้ดตัวอย่าง
#include <bits/stdc++.h>
using namespace std;

void findNintegers(int N, int A, int B) {
    vector<int> numbers;
    for (int i = 0; i < N - 1; i++)
        numbers.push_back(1);
    
    if (B - (N - 1) <= 0) {
        cout << "-1";
        return;
    }
    numbers.push_back(B - (N - 1));
    
    int vals = 0;
    for (int i = 0; i < N; i++)
        vals += numbers[i] * numbers[i];
    
    if (vals < A) {
        cout << "-1";
        return;
    }
    
    for (int i = 0; i < N; i++)
        cout << numbers[i] << " ";
}

int main() {
    int N = 4, A = 65, B = 17;
    cout << N << " positive integers that satisfy the given equations are ";
    findNintegers(N, A, B);
    return 0;
}

เอาต์พุต
4 positive integers that satisfy the given equations are 1 1 1 14

สรุป
Greedy: ทำให้ตัวเลขกระจายมากที่สุด (1 ตัวใหญ่, ที่เหลือเป็น 1) เพื่อเพิ่มผลรวมกำลังสอง