数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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。使用 floor 或 ceil 操作得到 (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0
为了解决这个问题，我们将遵循以下步骤 -
ret := 0
创建一个优先级队列 pq 用于 (double 和数组) 类型复杂数据
对于 i 在 0 到 prices 大小范围内
x := prices[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"
340 次查看
