রাউন্ডিং এরর মিনিমাইজ করে টার্গেট সেট করা (C++)

এই সমস্যায় একটি প্রাইস অ্যারে P এবং একটি টার্গেট ভ্যালু দেওয়া আছে। প্রতিটি প্রাইসকে ফ্লোর বা সিলিং করে রাউন্ড করতে হবে যাতে রাউন্ড করা অ্যারেটির যোগফল টার্গেটের সমান হয়। সবচেয়ে ছোট রাউন্ডিং এরর (অবсолют পার্থক্যের যোগফল) বের করতে হবে।

উদাহরণ

ইনপুট: ["0.700", "2.800", "4.900"], target = 8

আউটপুট: "1.000"

ব্যাখ্যা: (0.7-0) + (3-2.8) + (5-4.9) = 0.7 + 0.2 + 0.1 = 1.0

অ্যালগরিদম (গ্রিডি + প্রায়োরিটি কিউ)

1. প্রতিটি প্রাইসকে ফ্লোর করুন, টার্গেট থেকে বিয়োগ করুন, এরর যোগ করুন।
2. যেসব প্রাইস ইন্টিজার নয়, তাদের diff = (ceil - x) - (x - floor) ক্যালকুলেট করে মিন-হিপে রাখুন।
3. টার্গেট পূরণ করতে হলে সবচেয়ে ছোট diff वालাগুলো সিলিং-এ আপগ্রেড করুন।
4. ফাইনাল এরর ৩ দশমিক পর্যন্ত স্ট্রিং হিসেবে ফেরত দিন।

C++ প্রোগ্রাম

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

struct Comparator {
    bool operator()(double a, double b) { return !(a < b); } // মিন-হিপ
};

class Solution {
public:
    string minimizeError(vector<string>& prices, int target) {
        double error = 0;
        priority_queue<double, vector<double>, Comparator> pq;

        for (string& p : prices) {
            double x = stod(p);
            double fl = floor(x), cl = ceil(x);
            if (fl != cl) {
                double diff = (cl - x) - (x - fl);
                pq.push(diff);
            }
            target -= (int)fl;
            error += (x - fl);
        }

        if (target > (int)pq.size() || target < 0) return "-1";

        while (target--) {
            error += pq.top();
            pq.pop();
        }

        string s = to_string(error);
        size_t pos = s.find('.');
        return s.substr(0, pos + 4); // ৩ দশমিক
    }
};

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

আউটপুট

1.000