Giả sử ta có mảng giá P [p1,p2...,pn] và giá trị mục tiêu (target), ta phải làm tròn mỗi giá Pi thành Roundi(Pi) sao cho mảng làm tròn [Round1(P1),Round2(P2)...,Roundn(Pn)] có tổng bằng giá trị mục tiêu. Mỗi phép Roundi(pi) có thể là Floor(Pi) hoặc Ceil(Pi).
Trả về chuỗi "-1" nếu mảng làm tròn không thể có tổng bằng target. Ngược lại, trả về sai số làm tròn nhỏ nhất (dưới dạng chuỗi với ba chữ số sau dấu phẩy) được định nghĩa là:
$\displaystyle\sum\limits_{i-1}^n |Round_{i} (P_i) - P_i|$
Ví dụ: ["0.700", "2.800", "4.900"], target = 8. Dùng floor/ceil: (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0
Để giải quyết, ta thực hiện các bước sau:
ret := 0.
Tạo hàng đợi ưu tiên pq cho kiểu dữ liệu phức tạp (double và mảng).
Với i từ 0 đến kích thước prices:
x := giá trị double của prices[i].
low := floor của x.
high := ceil của x.
Nếu low khác high:
diff := (high - x) - (x - low).
Chèn diff vào pq.
target := target - low.
ret := ret + (x - low).
Nếu target > kích thước pq hoặc target < 0, trả về "-1".
Khi target khác 0:
ret := ret + đỉnh pq, xóa khỏi pq.
Giảm target đi 1.
s := ret dưới dạng chuỗi.
Trả về chuỗi con s lấy số đến ba chữ số thập phân.
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ minh họa
#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)); }Đầu vào
["0.700","2.800","4.900"] 8
Kết quả
"1.000"