2819. Minimum Relative Loss After Buying Chocolates
Description
You are given an integer array prices
, which shows the chocolate prices and a 2D integer array queries
, where queries[i] = [k_{i}, m_{i}]
.
Alice and Bob went to buy some chocolates, and Alice suggested a way to pay for them, and Bob agreed.
The terms for each query are as follows:
 If the price of a chocolate is less than or equal to
k_{i}
, Bob pays for it.  Otherwise, Bob pays
k_{i}
of it, and Alice pays the rest.
Bob wants to select exactly m_{i}
chocolates such that his relative loss is minimized, more formally, if, in total, Alice has paid a_{i}
and Bob has paid b_{i}
, Bob wants to minimize b_{i}  a_{i}
.
Return an integer array ans
where ans[i]
is Bob's minimum relative loss possible for queries[i]
.
Example 1:
Input: prices = [1,9,22,10,19], queries = [[18,4],[5,2]] Output: [34,21] Explanation: For the 1^{st} query Bob selects the chocolates with prices [1,9,10,22]. He pays 1 + 9 + 10 + 18 = 38 and Alice pays 0 + 0 + 0 + 4 = 4. So Bob's relative loss is 38  4 = 34. For the 2^{nd} query Bob selects the chocolates with prices [19,22]. He pays 5 + 5 = 10 and Alice pays 14 + 17 = 31. So Bob's relative loss is 10  31 = 21. It can be shown that these are the minimum possible relative losses.
Example 2:
Input: prices = [1,5,4,3,7,11,9], queries = [[5,4],[5,7],[7,3],[4,5]] Output: [4,16,7,1] Explanation: For the 1^{st} query Bob selects the chocolates with prices [1,3,9,11]. He pays 1 + 3 + 5 + 5 = 14 and Alice pays 0 + 0 + 4 + 6 = 10. So Bob's relative loss is 14  10 = 4. For the 2^{nd} query Bob has to select all the chocolates. He pays 1 + 5 + 4 + 3 + 5 + 5 + 5 = 28 and Alice pays 0 + 0 + 0 + 0 + 2 + 6 + 4 = 12. So Bob's relative loss is 28  12 = 16. For the 3^{rd} query Bob selects the chocolates with prices [1,3,11] and he pays 1 + 3 + 7 = 11 and Alice pays 0 + 0 + 4 = 4. So Bob's relative loss is 11  4 = 7. For the 4^{th} query Bob selects the chocolates with prices [1,3,7,9,11] and he pays 1 + 3 + 4 + 4 + 4 = 16 and Alice pays 0 + 0 + 3 + 5 + 7 = 15. So Bob's relative loss is 16  15 = 1. It can be shown that these are the minimum possible relative losses.
Example 3:
Input: prices = [5,6,7], queries = [[10,1],[5,3],[3,3]] Output: [5,12,0] Explanation: For the 1^{st} query Bob selects the chocolate with price 5 and he pays 5 and Alice pays 0. So Bob's relative loss is 5  0 = 5. For the 2^{nd} query Bob has to select all the chocolates. He pays 5 + 5 + 5 = 15 and Alice pays 0 + 1 + 2 = 3. So Bob's relative loss is 15  3 = 12. For the 3^{rd} query Bob has to select all the chocolates. He pays 3 + 3 + 3 = 9 and Alice pays 2 + 3 + 4 = 9. So Bob's relative loss is 9  9 = 0. It can be shown that these are the minimum possible relative losses.
Constraints:
1 <= prices.length == n <= 10^{5}
1 <= prices[i] <= 10^{9}
1 <= queries.length <= 10^{5}
queries[i].length == 2
1 <= k_{i} <= 10^{9}
1 <= m_{i} <= n
Solutions
Solution 1: Sorting + Binary Search + Prefix Sum
Based on the problem description, we know:
If $prices[i] \leq k$, then Bob needs to pay $prices[i]$, and Alice doesn’t need to pay. Therefore, Bob’s relative loss is $prices[i]$. In this case, Bob should choose the chocolate with a lower price to minimize the relative loss.
If $prices[i] > k$, then Bob needs to pay $k$, and Alice needs to pay $prices[i]  k$. Therefore, Bob’s relative loss is $k  (prices[i]  k) = 2k  prices[i]$. In this case, Bob should choose the chocolate with a higher price to minimize the relative loss.
Therefore, we first sort the price array $prices$, and then preprocess the prefix sum array $s$, where $s[i]$ represents the sum of the prices of the first $i$ chocolates.
Next, for each query $[k, m]$, we first use binary search to find the index $r$ of the first chocolate with a price greater than $k$. Then, we use binary search again to find the number of chocolates $l$ that should be chosen on the left, so the number of chocolates that should be chosen on the right is $m  l$. At this point, Bob’s relative loss is $s[l] + 2k(m  l)  (s[n]  s[n  (m  l)])$.
In the second binary search process mentioned above, we need to judge whether $prices[mid] < 2k  prices[n  (m  mid)]$, where $right$ represents the number of chocolates that should be chosen on the right. If this inequality holds, it means that choosing the chocolate at position $mid$ has a lower relative loss, so we update $l = mid + 1$. Otherwise, it means that the chocolate at position $mid$ has a higher relative loss, so we update $r = mid$.
The time complexity is $O((n + m) \times \log n)$, and the space complexity is $O(n)$. Where $n$ and $m$ are the lengths of the arrays $prices$ and $queries$, respectively.









