小红购物

[题目链接](https://www.nowcoder.com/practice/d4e0c4c4e5154787b7ddc9141d64deda)

思路

本题的核心是：对每件商品，在所有适用的优惠券中选一张折扣最大的使用。

优惠券 $(a_i, b_i)$ 对价格为 $p$ 的商品适用，当且仅当 $p \geq a_i$ ，此时可以减去 $b_i$ 。每件商品最多用一张券，每种券不限次数。

贪心 + 排序 + 二分

关键观察：对于价格为 $p$ 的商品，所有满足 $a_i \leq p$ 的优惠券都可以使用，我们只需要找到其中 $b_i$ 最大的那张即可。

做法：

将优惠券按门槛 $a$ 从小到大排序。
构造一个前缀最大折扣数组 $\text{maxDisc}[i]$ ：表示前 $i+1$ 张优惠券中折扣的最大值。即 $\text{maxDisc}[i] = \max(b_0, b_1, \ldots, b_i)$ 。
对于每件价格为 $p$ 的商品，二分查找门槛数组中最后一个 $\leq p$ 的位置 $\text{pos}$ 。若存在，最优折扣就是 $\text{maxDisc}[\text{pos}]$ ，商品实际花费 $p - \text{maxDisc}[\text{pos}]$ ；否则无券可用，花费 $p$ 。

样例演示

商品价格： $[4, 8, 6]$ ，优惠券： $[(5, 1), (8, 5)]$ 。

排序后优惠券按门槛： $[(5, 1), (8, 5)]$ ，前缀最大折扣： $[1, 5]$ 。

商品 $p=4$ ：二分查找 $\leq 4$ 的门槛，不存在，花 $4$ 。
商品 $p=8$ ：二分查找 $\leq 8$ 的最右位置为 $1$ ， $\text{maxDisc}[1] = 5$ ，花 $8 - 5 = 3$ 。
商品 $p=6$ ：二分查找 $\leq 6$ 的最右位置为 $0$ ， $\text{maxDisc}[0] = 1$ ，花 $6 - 1 = 5$ 。

总花费： $4 + 3 + 5 = 12$ 。

复杂度

时间复杂度： $O(m \log m + n \log m)$ ，排序优惠券 $O(m \log m)$ ，每件商品二分查找 $O(\log m)$ 。
空间复杂度： $O(n + m)$ ，存储商品价格和优惠券信息。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> p(n);
    for(int i = 0; i < n; i++) cin >> p[i];

    vector<pair<long long,long long>> coupons(m);
    for(int i = 0; i < m; i++) cin >> coupons[i].first >> coupons[i].second;

    sort(coupons.begin(), coupons.end());

    vector<long long> thresh(m), maxDisc(m);
    for(int i = 0; i < m; i++){
        thresh[i] = coupons[i].first;
        maxDisc[i] = coupons[i].second;
        if(i > 0) maxDisc[i] = max(maxDisc[i], maxDisc[i-1]);
    }

    long long ans = 0;
    for(int i = 0; i < n; i++){
        int lo = 0, hi = m - 1, pos = -1;
        while(lo <= hi){
            int mid = (lo + hi) / 2;
            if(thresh[mid] <= p[i]){
                pos = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        if(pos >= 0){
            ans += p[i] - maxDisc[pos];
        } else {
            ans += p[i];
        }
    }
    cout << ans << endl;
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] p = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            p[i] = Long.parseLong(st.nextToken());
        }

        long[][] coupons = new long[m][2];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            coupons[i][0] = Long.parseLong(st.nextToken());
            coupons[i][1] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(coupons, (a, b) -> Long.compare(a[0], b[0]));

        long[] thresh = new long[m];
        long[] maxDisc = new long[m];
        for (int i = 0; i < m; i++) {
            thresh[i] = coupons[i][0];
            maxDisc[i] = coupons[i][1];
            if (i > 0) maxDisc[i] = Math.max(maxDisc[i], maxDisc[i - 1]);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            int lo = 0, hi = m - 1, pos = -1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;
                if (thresh[mid] <= p[i]) {
                    pos = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
            if (pos >= 0) {
                ans += p[i] - maxDisc[pos];
            } else {
                ans += p[i];
            }
        }
        System.out.println(ans);
    }
}