最小化舍入误差以达到C ++中的目标
假设我们有一个价格数组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。使用下限或ceil运算获得(0.7-0)+(3-2.8)+(5-4.9)=0.7+0.2+0.1=1.0
为了解决这个问题，我们将遵循以下步骤-
ret：=0
为（双精度和数组）类型的复杂数据制作一个优先级队列pq
对于我来说，价格范围是0到
差异：=（高-x）–（x-低）
将diff插入pq
x：=价格的两倍[i]
低：=x的下限
高：=x的上限
如果低不高
目标：=目标–低
ret：=ret+（x-低）
如果目标>pq的大小或目标<0，则返回“-1”
而目标不为0
ret：=ret+pq顶部，从pq删除
d
将目标降低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"