最小化舍入误差以达到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"