LeetCode 1058. 最小化舍入误差以满足目标（排序+贪心）

示例 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"
解释：
达到目标是不可能的。
 
提示：
1 <= prices.length <= 500
表示价格的每个字符串 prices[i] 都代表一个介于 0 和 1000 之间的实数，
	并且正好有 3 个小数位。
target 介于 0 和 1000000 之间。

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