मान लीजिए हमारे पास कीमतों की एक सरणी P [p1,p2...,pn] और एक टारगेट वैल्यू है, हमें प्रत्येक कीमत Pi को Roundi(Pi) में राउंड करना है ताकि राउंडेड सरणी [Round1(P1),Round2(P2)...,Roundn(Pn)] का योग दिए गए टारगेट वैल्यू के बराबर हो। यहां प्रत्येक ऑपरेशन Roundi(pi) या तो Floor(Pi) या Ceil(Pi) हो सकता है।
यदि राउंडेड सरणी का योग टारगेट के बराबर करना असंभव है तो स्ट्रिंग "-1" लौटाएं। अन्यथा, सबसे छोटी राउंडिंग त्रुटि लौटाएं, जिसे (तीन दशमलव स्थानों के साथ स्ट्रिंग के रूप में) परिभाषित किया गया है:
$\displaystyle\sum\limits_{i-1}^n |Round_{i} (???? ) - ????$
इसलिए अगर इनपुट ["0.700", "2.800", "4.900"] है, और टारगेट 8 है। फ्लोर या सील ऑपरेशन का उपयोग करके (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 प्राप्त करें।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
ret := 0
(डबल और सरणी) प्रकार के जटिल डेटा के लिए एक प्रायोरिटी क्यू pq बनाएं
i को 0 से कीमतों के आकार तक रेंज में लिए:
x := कीमतों[i] का डबल मान
low := x का फ्लोर
high := x का सीलिंग
यदि low, high नहीं है
diff := (high - x) - (x - low)
diff को pq में डालें
target := target - low
ret := ret + (x - low)
यदि target > pq का आकार या target < 0, तो "-1" लौटाएं
जब तक target 0 नहीं है:
ret := ret + pq का टॉप, pq से हटाएं
- d
target को 1 से घटाएं
s := ret को स्ट्रिंग के रूप में
s का सबस्ट्रिंग लौटाएं जिसमें दशमलव के बाद तीन स्थान तक संख्या हो
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#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 ret = 0; priority_queue < double, vector < double >, Comparator > pq; for(int i = 0; i < prices.size(); i++){ double x = stod(prices[i]); double low = floor(x); double high = ceil(x); if(low != high){ double diff = ((high - x) - (x - low)); pq.push(diff); } target -= low; ret += (x - low); } if(target > pq.size() || target < 0) return "-1"; while(target--){ ret += pq.top(); pq.pop(); } string s = to_string (ret); return s.substr (0, s.find_first_of ('.', 0) + 4); } }; main(){ vector<string> v = {"0.700","2.800","4.900"}; Solution ob; cout << (ob.minimizeError(v, 8)); }इनपुट
["0.700","2.800","4.900"] 8
आउटपुट
"1.000"
