Welcome to Subscribe On Youtube
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.

class Solution { private int n; private int[] prices; public long[] minimumRelativeLosses(int[] prices, int[][] queries) { n = prices.length; Arrays.sort(prices); this.prices = prices; long[] s = new long[n + 1]; for (int i = 0; i < n; ++i) { s[i + 1] = s[i] + prices[i]; } int q = queries.length; long[] ans = new long[q]; for (int i = 0; i < q; ++i) { int k = queries[i][0], m = queries[i][1]; int l = f(k, m); int r = m  l; ans[i] = s[l] + 2L * k * r  (s[n]  s[n  r]); } return ans; } private int f(int k, int m) { int l = 0, r = Arrays.binarySearch(prices, k); if (r < 0) { r = (r + 1); } r = Math.min(m, r); while (l < r) { int mid = (l + r) >> 1; int right = m  mid; if (prices[mid] < 2L * k  prices[n  right]) { l = mid + 1; } else { r = mid; } } return l; } }

class Solution { public: vector<long long> minimumRelativeLosses(vector<int>& prices, vector<vector<int>>& queries) { int n = prices.size(); sort(prices.begin(), prices.end()); long long s[n + 1]; s[0] = 0; for (int i = 1; i <= n; ++i) { s[i] = s[i  1] + prices[i  1]; } auto f = [&](int k, int m) { int l = 0, r = upper_bound(prices.begin(), prices.end(), k)  prices.begin(); r = min(r, m); while (l < r) { int mid = (l + r) >> 1; int right = m  mid; if (prices[mid] < 2LL * k  prices[n  right]) { l = mid + 1; } else { r = mid; } } return l; }; vector<long long> ans; for (auto& q : queries) { int k = q[0], m = q[1]; int l = f(k, m); int r = m  l; ans.push_back(s[l] + 2LL * k * r  (s[n]  s[n  r])); } return ans; } };

class Solution: def minimumRelativeLosses( self, prices: List[int], queries: List[List[int]] ) > List[int]: def f(k: int, m: int) > int: l, r = 0, min(m, bisect_right(prices, k)) while l < r: mid = (l + r) >> 1 right = m  mid if prices[mid] < 2 * k  prices[n  right]: l = mid + 1 else: r = mid return l prices.sort() s = list(accumulate(prices, initial=0)) ans = [] n = len(prices) for k, m in queries: l = f(k, m) r = m  l loss = s[l] + 2 * k * r  (s[n]  s[n  r]) ans.append(loss) return ans

func minimumRelativeLosses(prices []int, queries [][]int) []int64 { n := len(prices) sort.Ints(prices) s := make([]int, n+1) for i, x := range prices { s[i+1] = s[i] + x } f := func(k, m int) int { l, r := 0, sort.Search(n, func(i int) bool { return prices[i] > k }) if r > m { r = m } for l < r { mid := (l + r) >> 1 right := m  mid if prices[mid] < 2*kprices[nright] { l = mid + 1 } else { r = mid } } return l } ans := make([]int64, len(queries)) for i, q := range queries { k, m := q[0], q[1] l := f(k, m) r := m  l ans[i] = int64(s[l] + 2*k*r  (s[n]  s[nr])) } return ans }

function minimumRelativeLosses(prices: number[], queries: number[][]): number[] { const n = prices.length; prices.sort((a, b) => a  b); const s: number[] = Array(n).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] + prices[i]; } const search = (x: number): number => { let l = 0; let r = n; while (l < r) { const mid = (l + r) >> 1; if (prices[mid] > x) { r = mid; } else { l = mid + 1; } } return l; }; const f = (k: number, m: number): number => { let l = 0; let r = Math.min(search(k), m); while (l < r) { const mid = (l + r) >> 1; const right = m  mid; if (prices[mid] < 2 * k  prices[n  right]) { l = mid + 1; } else { r = mid; } } return l; }; const ans: number[] = []; for (const [k, m] of queries) { const l = f(k, m); const r = m  l; ans.push(s[l] + 2 * k * r  (s[n]  s[n  r])); } return ans; }