文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一系列價(jià)格 [p1,p2…,pn] 和一個(gè)目標(biāo) target，將每個(gè)價(jià)格 pi 舍入為 Roundi(pi) 以使得舍入數(shù)組 [Round1(p1),Round2(p2)...,Roundn(pn)] 之和達(dá)到給定的目標(biāo)值 target。每次舍入操作 Roundi(pi) 可以是向下舍 Floor(pi) 也可以是向上入 Ceil(pi)。

如果舍入數(shù)組之和無(wú)論如何都無(wú)法達(dá)到目標(biāo)值 target，就返回 -1。
否則，以保留到小數(shù)點(diǎn)后三位的字符串格式返回最小的舍入誤差，其定義為 Σ |Roundi(pi) - (pi)|（ i 從 1 到 n ）。

示例 1： 輸入：prices = ["0.700","2.800","4.900"], target = 8 輸出："1.000" 解釋： 使用 Floor，Ceil 和 Ceil 操作得到 (0.7 - 0) + (3 - 2.8) + (5 - 4.9) = 0.7 + 0.2 + 0.1 = 1.0 。示例 2： 輸入：prices = ["1.500","2.500","3.500"], target = 10 輸出："-1" 解釋： 達(dá)到目標(biāo)是不可能的。提示： 1 <= prices.length <= 500 表示價(jià)格的每個(gè)字符串 prices[i] 都代表一個(gè)介于 0 和 1000 之間的實(shí)數(shù)，并且正好有 3 個(gè)小數(shù)位。 target 介于 0 和 1000000 之間。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimize-rounding-error-to-meet-target
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

class Solution { public:string minimizeError(vector<string>& prices, int target) {vector<int> decimal;int num;for(string& p : prices){target -= stoi(p);//先把整數(shù)部分減去num = stoi(p.substr(p.size()-3));if(num != 0)decimal.push_back(num);//有小數(shù)的}if(target > decimal.size())//全部向上取整都不夠的return "-1";if(target < 0)//全部向下取整，和還超過(guò)targetreturn "-1";sort(decimal.rbegin(), decimal.rend());//大的在前面（靠近1）int error = 0;for(int i = 0; i < decimal.size(); ++i)//所有非0的小數(shù)都要取整{if(target > 0)error += 1000-decimal[i],//向上取整，大的小數(shù)優(yōu)先target--;else if(target == 0)//不需要了，全部舍棄小數(shù)error += decimal[i];}char ch[8];//最多500，3位+.1位+3小數(shù)+\0 1位 = 8sprintf(ch, "%.3f", double(error)/1000);return string(ch);} };

4 ms 7.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1058. 最小化舍入误差以满足目标（排序+贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。