ลดข้อผิดพลาดในการปัดเศษให้น้อยที่สุดเพื่อให้ตรงตามเป้าหมายใน 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 ใช้การดำเนินการพื้นหรือเพดานเพื่อรับ (0.7 - 0) + (3 - 2.8) + (5 - 4.9) =0.7 + 0.2 + 0.1 =1.0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=0

• สร้างคิวลำดับความสำคัญ pq สำหรับประเภทข้อมูลที่ซับซ้อน (ดับเบิลและอาร์เรย์)

• สำหรับผมอยู่ในช่วง 0 ถึงขนาดของราคา

  • x :=มูลค่าสองเท่าของราคา[i]

  • ต่ำ :=ชั้นของ x

  • สูง :=เพดาน x

  • ถ้าต่ำไม่สูง

    • diff :=(สูง - x) – (x - ต่ำ)

    • แทรก diff ลงใน pq

  • เป้าหมาย :=เป้าหมาย – ต่ำ

  • ret :=ret + (x - ต่ำ)

• ถ้าเป้าหมาย> ขนาดของ pq หรือเป้าหมาย <0 ให้คืนค่า “-1”

• ในขณะที่เป้าหมายไม่ใช่ 0

  • ret :=ret + ด้านบนของ pq ลบออกจาก pq

  • ด

  • ลดเป้าหมาย 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"