思路：排序+双指针

贪心，只要一个商品的价格达到了优惠券使用的最低价格，那么这件商品就可以用这张优惠券。

因为减的价格都是一样的，所以给哪个商品用都可以。

但是价格越高的商品越能满足最低价格越高的优惠券，所以我们将优惠券和商品都按价格从小到大排序。

然后按价格从小到大来枚举商品，找到所有的最低价格小于等于这个商品，从中找到一个优惠价格最大的，使用即可。

这部分用双指针来维护，即不断移动指向优惠券的指针直到其最低价格大于当前商品价格停止。

时间复杂度：$O(nlogn)$

代码

C++

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> p(n);
    vector<pair<int, int>> ab(m);

    for (int i = 0; i < n; ++i) cin >> p[i];
    for (int i = 0; i < m; ++i) {
        cin >> ab[i].first >> ab[i].second;
    }

    sort(ab.begin(), ab.end());
    sort(p.begin(), p.end());

    long long ans = 0;
    int maxsub = 0;

    // 对于每个商品，找到大于等于最低要求的，优惠最大的优惠券即可
    for (int i = 0, j = 0; i < n; ++i) {

        // 取到所有最低使用价格小于等于当前价格的优惠券的优惠值
        while (j < m && p[i] >= ab[j].first) {
            maxsub = max(maxsub, ab[j].second);
            j += 1;
        }

        ans += p[i] - maxsub;
    }

    cout << ans << "\n";

    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Description:
 * @Auther: XiaoShe
 * @DateTime: 2023/11/28 22:14
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        long[] p = new long[n];
        long res = 0L;
        for (int i = 0; i < n; i++) {
            p[i] = scanner.nextInt();
            res += p[i];
        }

        Pair[] pairs = new Pair[m];
        for (int i = 0; i < m; i++) {
            long x = scanner.nextLong();
            long y = scanner.nextLong();
            pairs[i] = new Pair(x, y);
        }

        Arrays.sort(pairs, (a, b)-> Long.compare(a.x,b.x));

        Arrays.sort(p);

        long flag = 0L;
        for (int i = 0, j = 0; i < n; i++) {
            while(j < m && p[i] >= pairs[j].x){
                flag = Math.max(flag, pairs[j++].y);
            }
            res -= flag;
        }

        System.out.println(res);

    }

    static class Pair{
        long x, y;
        Pair(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

}

Python

n, m = list(map(int, input().split()))
shoppings = list(map(int, input().split()))
quan = []
for i in range(m):
    quan.append(list(map(int, input().split())))

quan.sort(key = lambda x : x[0])
shoppings.sort()
res = 0
index = 0
max_cut = 0
for shopping in shoppings:
    while index < m and quan[index][0] <= shopping:
        max_cut = max(max_cut, quan[index][1])
        index += 1
    res += shopping - max_cut
print(res)