Minimize Rounding Error เพื่อให้ผลรวมเท่ากับ Target ใน C++

ปัญหา

ให้ Array ราคา P และ Target ให้ปัดแต่ละราคาเป็น Floor หรือ Ceil ผลรวมต้องเท่ากับ Target หา Rounding Error น้อยที่สุด

Error = Σ |Round(Pᵢ) - Pᵢ| คืนเป็น String 3 ทศนิยม

ตัวอย่าง

P = ["0.700", "2.800", "4.900"], Target = 8

Floor: 0, 2, 4 = 6 → ต้อง Ceil อีก 2 ตัว

เลือก Ceil ที่ Error เพิ่มน้อยที่สุด: 2.8→3 (+0.2), 4.9→5 (+0.1)

Error = 0.7 + 0.2 + 0.1 = 1.000

อัลกอริทึม: Greedy + Priority Queue

1. ปัด Floor ทุกตัว คำนวณ Error รวม และ Target ที่เหลือ
2. สำหรับตัวที่ Floor ≠ Ceil คำนวณ "Extra Error" ถ้าเปลี่ยนเป็น Ceil
3. Extra Error = (Ceil - x) - (x - Floor) = Ceil + Floor - 2x
4. เลือกตัวที่ Extra Error น้อยที่สุด (Min Heap) จนครบ Target

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

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

struct Comparator {
    bool operator()(double a, double b) { return a > b; } // Min Heap
};

class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        double error = 0;
        priority_queue<double, vector<double>, Comparator> pq;
        
        for (string& s : prices) {
            double x = stod(s);
            double fl = floor(x), cl = ceil(x);
            
            if (fl != cl) {
                double extra = (cl - x) - (x - fl); // Cost เพิ่มถ้า Ceil
                pq.push(extra);
            }
            
            target -= fl;
            error += x - fl;
        }
        
        if (target < 0 || target > (int)pq.size()) return "-1";
        
        while (target-- > 0) {
            error += pq.top();
            pq.pop();
        }
        
        // Format to 3 decimal places
        char buf[32];
        snprintf(buf, sizeof(buf), "%.3f", error);
        return string(buf);
    }
};

int main() {
    Solution ob;
    vector<string> v = {"0.700", "2.800", "4.900"};
    cout << ob.minimizeError(v, 8) << endl; // "1.000"
    return 0;
}

ผลลัพธ์

1.000

Edge Cases

• Target < Sum(Floor) หรือ Target > Sum(Ceil) → "-1"
• ราคาเป็น Integer แล้ว → Floor=Ceil ไม่เข้า PQ