跳转至

2819. 购买巧克力后的最小相对损失 🔒

难度困难

题目描述

现给定一个整数数组 prices，表示巧克力的价格；以及一个二维整数数组 queries，其中 queries[i] = [ki, mi]。

Alice 和 Bob 去买巧克力，Alice 提出了一种付款方式，而 Bob 同意了。

对于每个 queries[i] ，它的条件如下：

  • 如果一块巧克力的价格 小于等于 ki，那么 Bob 为它付款。
  • 否则，Bob 为其中 ki 部分付款，而 Alice 为 剩余 部分付款。

Bob 想要选择 恰好 mi 块巧克力，使得他的 相对损失最小 。更具体地说，如果总共 Alice 付款了 ai，Bob 付款了 bi，那么 Bob 希望最小化 bi - ai。

返回一个整数数组 ans，其中 ans[i] 是 Bob 在 queries[i] 中可能的 最小相对损失 。

 

示例 1：

输入：prices = [1,9,22,10,19], queries = [[18,4],[5,2]]
输出：[34,-21]
解释：对于第一个 query，Bob 选择价格为 [1,9,10,22] 的巧克力。他付了 1 + 9 + 10 + 18 = 38，Alice 付了 0 + 0 + 0 + 4 = 4。因此，Bob 的相对损失是 38 - 4 = 34。
对于第二个 query，Bob 选择价格为 [19,22] 的巧克力。他付了 5 + 5 = 10，Alice 付了 14 + 17 = 31。因此，Bob 的相对损失是 10 - 31 = -21。
可以证明这些是可能的最小相对损失。

示例 2：

输入：prices = [1,5,4,3,7,11,9], queries = [[5,4],[5,7],[7,3],[4,5]]
输出：[4,16,7,1]
解释：对于第一个 query，Bob 选择价格为 [1,3,9,11] 的巧克力。他付了 1 + 3 + 5 + 5 = 14，Alice 付了 0 + 0 + 4 + 6 = 10。因此，Bob 的相对损失是 14 - 10 = 4。
对于第二个 query，Bob 必须选择所有的巧克力。他付了 1 + 5 + 4 + 3 + 5 + 5 + 5 = 28，Alice 付了 0 + 0 + 0 + 0 + 2 + 6 + 4 = 12。因此，Bob 的相对损失是 28 - 12 = 16。
对于第三个 query，Bob 选择价格为 [1,3,11] 的巧克力。他付了 1 + 3 + 7 = 11，Alice 付了 0 + 0 + 4 = 4。因此，Bob 的相对损失是 11 - 4 = 7。
对于第四个 query，Bob 选择价格为 [1,3,7,9,11] 的巧克力。他付了 1 + 3 + 4 + 4 + 4 = 16，Alice 付了 0 + 0 + 3 + 5 + 7 = 15。因此，Bob 的相对损失是 16 - 15 = 1。
可以证明这些是可能的最小相对损失。

示例 3：

输入：prices = [5,6,7], queries = [[10,1],[5,3],[3,3]]
输出：[5,12,0]
解释：对于第一个 query，Bob 选择价格为 5 的巧克力。他付了 5，Alice 付了 0。因此，Bob 的相对损失是 5 - 0 = 5。
对于第二个 query，Bob 必须选择所有的巧克力。他付了 5 + 5 + 5 = 15，Alice 付了 0 + 1 + 2 = 3。因此，Bob 的相对损失是 15 - 3 = 12。
对于第三个 query，Bob 必须选择所有的巧克力。他付了 3 + 3 + 3 = 9，Alice 付了 2 + 3 + 4 = 9。因此，Bob 的相对损失是 9 - 9 = 0。
可以证明这些是可能的最小相对损失。

 

提示：

  • 1 <= prices.length == n <= 105
  • 1 <= prices[i] <= 109
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 1 <= ki <= 109
  • 1 <= mi <= n

解法

方法一：排序 + 二分查找 + 前缀和

思考

每次询问在阈值 \(k\) 下购买 \(m\) 块巧克力。相对损失在 \(\textit{price}\le k\) 时为价格本身，在 \(\textit{price}>k\) 时为 \(2k-\textit{price}\)。最优组合是若干最便宜的与若干最贵的；排序并维护前缀和后，二分分界点即可在每次询问中算出损失。

根据题目描述，我们可以知道：

如果 \(\textit{prices}[i] \leq k\)，那么 Bob 需要支付 \(\textit{prices}[i]\)，而 Alice 不需要支付。因此 Bob 的相对损失为 \(\textit{prices}[i]\)。在这种情况下，Bob 应该选择价格较低的巧克力，才能最小化相对损失。

如果 \(\textit{prices}[i] \gt k\)，那么 Bob 需要支付 \(k\)，而 Alice 需要支付 \(\textit{prices}[i] - k\)。因此 Bob 的相对损失为 \(k - (\textit{prices}[i] - k) = 2k - \textit{prices}[i]\)。在这种情况下，Bob 应该选择价格较高的巧克力，才能最小化相对损失。

因此，我们先对价格数组 \(\textit{prices}\) 进行排序，然后预处理出前缀和数组 \(s\)，其中 \(s[i]\) 表示前 \(i\) 个巧克力的价格之和。

接下来，对于每个询问 \([k, m]\)，我们先使用二分查找，找到第一个价格大于 \(k\) 的巧克力的下标 \(r\)。然后，再利用二分查找，找到左侧应该选择的巧克力的数量 \(l\)，那么右侧应该选择的巧克力的数量就是 \(m - l\)。此时，Bob 的相对损失为 \(s[l] + 2k(m - l) - (s[n] - s[n - (m - l)])\)。

上述第二次二分查找的过程中，我们需要判断 \(\textit{prices}[\textit{mid}] \lt 2k - \textit{prices}[n - (m - \textit{mid})]\)，其中 \(\textit{right}\) 表示右侧应该选择的巧克力的数量。如果该不等式成立，那么说明选择 \(\textit{mid}\) 位置的巧克力的相对损失较低，此时更新 \(l = \textit{mid} + 1\)。否则，说明 \(\textit{mid}\) 位置的巧克力的相对损失较高，此时更新 \(r = \textit{mid}\)。

时间复杂度 \(O((n + m) \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 和 \(m\) 分别是数组 \(\textit{prices}\) 和 \(\textit{queries}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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*k-prices[n-right] {
                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[n-r]))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
}

评论