Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Round prices
/* #18 Round Prices Given an array of numbers A = [x1, x2, ..., xn] and T = Round(x1+x2+... +xn). We want to find a way to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1+y2+...+yn = T where yi = Floor(xi) or Ceil(xi), ceiling or floor of xi. We also want to minimize sum |x_i-y_i| */ #include <iostream> #include <vector> #include <math.h> #include <algorithm> using namespace std; bool compare(pair<double, int>& a, pair<double,int>& b){ return a.first < b.first; } vector<int> round(vector<double>& v){ double sum = 0.0; for(auto x: v) sum += x; int target = round(sum); int sumFloor = 0; vector<pair<double,int>> error; // abs, idx vector<int> res(v.size(),0); for(int i=0; i<(int)v.size(); i++){ double x = v[i]; sumFloor += floor(x); error.push_back({ceil(x)-x, i}); res[i] = floor(x); } int delta = target - sumFloor; sort(error.begin(), error.end(), compare); for(int i=0; i<delta; i++) { int id = error[i].second; res[id]++; } return res; } void print(vector<double> v, vector<int> res){ for(auto x: v) cout << x << ",\t" ; cout << endl; for(auto x: res) cout<< x << ",\t"; cout<< endl; } int main(){ vector<double> v = {0.1, 0.8, 0.4, 0.7}; vector<int> res = round(v); print(v,res); return 0; }
run
|
edit
|
history
|
help
0
precision and fixed point notation
Rotate90
ww999
Hi
nearest
Const Return Test
synowie abrahama
Geometric Series
ulib
remove_if_30-Seconds-of-C++