python adjusted subtotals sum to the rounded total price-CodePudding

I have this python function question that I can't seem to wrap my head around. Write a function that takes a list of prices, prices, and finds the floor or ceiling of each price[i] so that the adjusted subtotals sum to the rounded total price and the adjusted subtotals are also as close to the original subtotals as possible. Phrased mathematically, you should minimize the sum of the absolute differences of the adjusted subtotals from the original subtotals. Return the list with the adjusted subtotals. (yeah a mouthful, right)

Example input:

prices: [5.40, 3.30, 5.00]

Example output:

[6, 3, 5]

Explanation:

5.40   3.30   5.00 = 13.70
13.70 is rounded to 14
The way to get 14 while adjusting the prices the least is ceil(5.40) and floor(3.30).

the below code is as far as I got, I'm not exactly sure what's next

prices = [5.40,3.30, 5.00]
total_price = 0
for price in prices:
    total_price =price

total_avg = round(total_price)
print("total_avg:",total_avg)

prices.sort()
min_price = prices[0]
max_price = prices[-1]

print("min_price:",min_price)
print("max_price:",max_price)

>>>total_avg: 14
>>>min_price: 3.3
>>>max_price: 5.4

CodePudding user response：

We can do that in O(nlog(n)) time easily. First we calculate sum of the numbers without their decimals, then we calculate the required rounded sum, we find out their difference. We then sort the values of their difference in ascending order then we get the ceil of those numbers which have higher decimal so their absolute diff is minimized and get floor of those numbers with lower decimal values. We use binary search to find out those numbers with higher decimal values.Each of those bisect calls will take log(n) time so our overall complexity is nLog(n) and the overall order of the array is still preserved.

import math
import bisect

prices = [5.40,3.30, 5.00]
ans = round(sum(prices))
pure_sum = sum([math.floor(i) for i in prices])
diff = ans-pure_sum
abs_diff = sorted([i-math.floor(i) for i in prices if (i%1!=0)])
for i in range(len(prices)):
    if bisect.bisect(abs_diff,prices[i]-math.floor(prices[i])) > diff:
        prices[i] = math.ceil(prices[i])
    else:
        prices[i] = math.floor(prices[i])

print(prices)