Round Numbers

Round Numbers

Input : array of decimals ~ X
Output : array of int ~ Y

But they need to satisfy the condition:

sum(Y) = round(sum(x))
minmize (|y1-x1| + |y2-x2| + … + |yn-xn|)

Example 1:
input = 30.3, 2.4, 3.5
output = 30 2 4

Example 2:
input = 30.9, 2.4, 3.9
output = 31 2 4

test

Solution

Select one round direction and then make up for the gap between the current sum and its original round sum.
If we select floor then the gap will be made up by the ceiling.

Note The biggest gap between the floor and original number is the smallest gap between the ceiling and original numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
using namespace std;
vector<int> roundDouble(vector<double> input) {
vector<int> res;
if(input.size()==0) return res;
if(input.size()==1) { res.push_back(round(input[0])); return res; }
res.resize(input.size());
double inputSum = accumulate(input.begin(),input.end(),0.0);
int sum = round(inputSum);
int lessSum = 0;
vector<pair<int,double>> diffPair;
for(int i=0;i<input.size();i++) {
lessSum += (res[i] = floor(input[i]));
double diff = input[i] - res[i];
diffPair.emplace_back(i,diff);
}
sort(diffPair.begin(), diffPair.end(), [](const pair<int, double>& p1, const pair<int, double>& p2) { return p1.second < p2.second; }); // diff will be in ascending order;
int gap = sum - lessSum;
for(int i=input.size()-gap;i<input.size();i++)
res[diffPair[i].first]++; // turn the floor to ceiling;
return res;
}
int main(int argc, char *argv[])
{
vector<double> input{30.3, 2.4, 3.5};
vector<int> output = roundDouble(input);
for(int i = 0; i < output.size(); ++i) cout<<output[i]<<", ";
cout<<endl;
return 0;
}

Always welcome new ideas and practical tricks, just leave them in the comments!