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 |라운드_{i} (???? ) - ????$

따라서 입력이 ["0.700", "2.800", "4.900"]이고 목표가 8인 경우 바닥 또는 천장 연산을 사용하여 (0.7 - 0) + (3 - 2.8) + (5 - 4.9) =0.7 + 0.2 + 0.1 =1.0

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret :=0

• (이중 및 배열) 유형의 복합 데이터에 대해 하나의 우선 순위 큐 pq를 만듭니다.

• 범위 0에서 가격 크기까지의 i에 대해

  • x :=가격의 두 배 값[i]

  • 낮음 :=x의 바닥

  • 높음 :=x의 상한

  • 낮음이 높지 않은 경우

    • diff :=(높음 - x) – (x - 낮음)

    • pq에 diff 삽입

  • 대상 :=대상 – 낮음

  • ret :=ret + (x - 낮음)

• target> size of pq 또는 target <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"