C++でターゲットを満たすために丸め誤差を最小化する

価格P[p1、p2 ...、pn]の配列とターゲット値があるとすると、丸められた配列[Round1（P1）、Round2（P2）になるように、各価格PiをRoundi（Pi）に丸める必要があります。 ...、Roundn（Pn）]は、指定されたターゲット値に合計されます。ここで、各操作Roundi（pi）は、Floor（Pi）またはCeil（Pi）のいずれかになります。

丸められた配列を合計してターゲットにできない場合は、文字列「-1」を返す必要があります。それ以外の場合は、最小の丸め誤差を返します。これは、（小数点以下3桁の文字列として）-

$ \ displaystyle \ sum \ Limits_ {i-1} ^ n | Round_ {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

• （doubleおよびarray）タイプの複合データに対して1つの優先キューpqを作成します

• 0から価格のサイズまでの範囲のiの場合

  • x：=価格の2倍の値[i]

  • 低：=xの床

  • 高：=xの天井

  • 低が高でない場合

    • diff：=（high-x）–（x-low）

    • pqにdiffを挿入します

  • ターゲット：=ターゲット–低

  • ret：=ret +（x-低）

• ターゲット>pqのサイズまたはターゲット<0の場合、「-1」を返します

• ターゲットが0ではない場合

  • ret：=ret + pqの先頭、pqから削除

  • d

  • ターゲットを1つ減らします

• s：=ret as string

• 小数点以下3桁までの数値を使用して部分文字列を返します

理解を深めるために、次の実装を見てみましょう-

例

#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"