Round prices, C++ (gcc)

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

λ

                                      .NET NoSQL database for rapid development