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
MemCpyClass
Logical AND versus Bitwise AND
5345
C++ Solar eclipse program(Shoushi integrated) 1568 - 1644 also check Lunar eclipse for Xing Yunlu
scuba
Clementina
Wuninitialized
Minimum number of jumps DP
Dejalo a la Suerte
queue