Tối thiểu hóa tổng nghiệm đa thức trong C++

Cho mảng hệ số đa thức (bậc n-1). Sắp xếp lại hệ số để tổng nghiệm (theo Vieta: -a_{n-1}/a_n) nhỏ nhất.

Ví dụ

Đầu vào: arr[] = {2, -1, 4, 9, -1, 10, -5} (bậc 6)

Đầu ra: -1 -5 2 4 9 -1 10

Giải thích: Đa thức: -1·x⁶ -5·x⁵ +2·x⁴ +4·x³ +9·x² -1·x +10. Tổng nghiệm = -(-5)/(-1) = -5 (tối thiểu).

Đầu vào: arr[] = {3, -2, -1, 4}

Đầu ra: -1 -2 3 4

Giải thích: -1·x³ -2·x² +3·x +4. Tổng nghiệm = -(-2)/(-1) = -2.

Phương pháp

• Tách hệ số dương (vec2) và âm (vec3).
• Nếu cả 2 đều ≥2 phần tử: tìm max/min của nhóm dương, max/min tuyệt đối của nhóm âm. So sánh tỷ số -max/min để chọn nhóm cho 2 hệ số dẫn đầu (cao nhất).
• Nếu chỉ 1 nhóm ≥2: dùng nhóm đó.
• Đưa 2 hệ số chọn lên đầu (hệ số bậc cao nhất), phần còn lại giữ nguyên thứ tự.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

void Minimize_root(int arr[], int size) {
    vector<int> pos, neg, res;
    for (int i=0; i 0) pos.push_back(i);
        else if (arr[i] < 0) neg.push_back(i);
    }
    if (pos.size() >= 2 && neg.size() >= 2) {
        // tìm max/min dương
        int maxP = INT_MIN, idxMaxP=-1, minP=INT_MAX, idxMinP=-1;
        for (int i: pos) if (arr[i] > maxP) {maxP=arr[i]; idxMaxP=i;}
        for (int i: pos) if (arr[i] < minP && i!=idxMaxP) {minP=arr[i]; idxMinP=i;}
        // tìm max/min tuyệt đối âm
        int maxN = INT_MIN, idxMaxN=-1, minN=INT_MAX, idxMinN=-1;
        for (int i: neg) if (abs(arr[i]) > maxN) {maxN=abs(arr[i]); idxMaxN=i;}
        for (int i: neg) if (abs(arr[i]) < minN && i!=idxMaxN) {minN=abs(arr[i]); idxMinN=i;}
        double ratioP = -1.0 * maxP / minP;
        double ratioN = -1.0 * maxN / minN;
        if (ratioP < ratioN) {
            res.push_back(arr[idxMinP]); res.push_back(arr[idxMaxP]);
            for (int i=0; i= 2) {
        // chỉ dùng nhóm dương
        int maxP=INT_MIN, idxMaxP=-1, minP=INT_MAX, idxMinP=-1;
        for (int i: pos) if (arr[i] > maxP) {maxP=arr[i]; idxMaxP=i;}
        for (int i: pos) if (arr[i] < minP && i!=idxMaxP) {minP=arr[i]; idxMinP=i;}
        res.push_back(arr[idxMinP]); res.push_back(arr[idxMaxP]);
        for (int i=0; i= 2) {
        // chỉ dùng nhóm âm
        int maxN=INT_MIN, idxMaxN=-1, minN=INT_MAX, idxMinN=-1;
        for (int i: neg) if (abs(arr[i]) > maxN) {maxN=abs(arr[i]); idxMaxN=i;}
        for (int i: neg) if (abs(arr[i]) < minN && i!=idxMaxN) {minN=abs(arr[i]); idxMinN=i;}
        res.push_back(arr[idxMinN]); res.push_back(arr[idxMaxN]);
        for (int i=0; i

Đầu ra chương trình
Minimize the sum of roots of a given polynomial is: -1 -5 2 4 9 -1 10