資料結構
網路
關係資料庫管理系統 (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 次檢視
