题目链接

小红购物

题目描述

小红准备买 件物品，第 件物品的价格是 。

另外，小红有 种优惠券，第 种优惠券的信息为 ，表示：买一件价格不小于 的商品时，可以减去 的价格。

  • 每件商品最多只能用一次优惠券。
  • 每种优惠券可以用多次（用于不同的商品）。

小红想知道，自己买下全部 件商品最少需要花多少钱？

解题思路

这是一个典型的贪心问题。我们的目标是最小化总花费，这等价于最大化总折扣。

1. 单件商品的最优策略

对于任何一件商品，要想让它的最终价格最低，我们就应该为它匹配一张能提供最大折扣的、并且可用的优惠券。

一张优惠券 对于价格为 的商品是“可用”的，当且仅当 。

因此，对于价格为 的商品，我们能获得的最大折扣就是所有可用优惠券中 值最大的那一个。

2. 高效匹配算法：排序 + 双指针

如果对每件商品都遍历所有优惠券来寻找最优匹配，总复杂度将是 ，会超时。我们可以通过排序进行优化。

核心思想是：如果一张优惠券对价格较低的商品可用，那么它对所有价格更高的商品也一定可用。

这启发我们使用双指针算法：

  1. 排序：

    • 将所有商品按价格 从小到大排序。
    • 将所有优惠券按使用门槛 从小到大排序。

  2. 双指针扫描：

    • 我们用一个指针 i 遍历排序后的商品，另一个指针 j 遍历排序后的优惠券。
    • 同时，我们维护一个变量 max_y_so_far，用于记录对于当前商品 a[i] 而言，所有可用的优惠券中最大的折扣额。
    • 当处理商品 a[i] 时，我们移动指针 j，将所有门槛 x[j] 小于等于 a[i] 的优惠券都纳入考虑范围，并用它们的折扣 y[j] 来更新 max_y_so_far。
    • 由于商品和优惠券都已排序，指针 j 在整个过程中只会前进，不会后退。
    • 对于当前的商品 a[i]，能享受到的最大折扣就是此时的 max_y_so_far。我们将这个折扣累加到总折扣 total_discount 中。

  3. 计算结果：

    • 首先计算出所有商品的原始总价。
    • 然后减去通过上述方法计算出的最大总折扣，即可得到最小总花费。

注意，总价和总折扣可能会超过32位整型的范围，需要使用64位整型（long long）进行计算。

代码

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

struct Coupon {
    int x, y;
};

bool compareCoupons(const Coupon& a, const Coupon& b) {
    return a.x < b.x;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<long long> a(n);
    long long initial_total_cost = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        initial_total_cost += a[i];
    }

    vector<Coupon> coupons(m);
    for (int i = 0; i < m; ++i) {
        cin >> coupons[i].x >> coupons[i].y;
    }

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

    long long total_discount = 0;
    int coupon_ptr = 0;
    long long max_y_so_far = 0;

    for (int i = 0; i < n; ++i) {
        // 找到所有适用于当前商品 a[i] 的优惠券，并更新最大折扣
        while (coupon_ptr < m && coupons[coupon_ptr].x <= a[i]) {
            max_y_so_far = max(max_y_so_far, (long long)coupons[coupon_ptr].y);
            coupon_ptr++;
        }
        total_discount += max_y_so_far;
    }

    cout << initial_total_cost - total_discount << endl;

    return 0;
}

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

class Coupon {
    int x, y;
    public Coupon(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        long[] a = new long[n];
        long initialTotalCost = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            initialTotalCost += a[i];
        }

        Coupon[] coupons = new Coupon[m];
        for (int i = 0; i < m; i++) {
            coupons[i] = new Coupon(sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(a);
        Arrays.sort(coupons, Comparator.comparingInt(c -> c.x));

        long totalDiscount = 0;
        int couponPtr = 0;
        long maxYSoFar = 0;

        for (int i = 0; i < n; i++) {
            while (couponPtr < m && coupons[couponPtr].x <= a[i]) {
                maxYSoFar = Math.max(maxYSoFar, coupons[couponPtr].y);
                couponPtr++;
            }
            totalDiscount += maxYSoFar;
        }

        System.out.println(initialTotalCost - totalDiscount);
    }
}

import sys

def solve():
    try:
        n, m = map(int, sys.stdin.readline().split())
        a = list(map(int, sys.stdin.readline().split()))
        
        coupons = []
        for _ in range(m):
            x, y = map(int, sys.stdin.readline().split())
            coupons.append((x, y))
            
        a.sort()
        coupons.sort() # sort by x by default
        
        initial_total_cost = sum(a)
        total_discount = 0
        coupon_ptr = 0
        max_y_so_far = 0
        
        for i in range(n):
            item_price = a[i]
            while coupon_ptr < m and coupons[coupon_ptr][0] <= item_price:
                max_y_so_far = max(max_y_so_far, coupons[coupon_ptr][1])
                coupon_ptr += 1
            total_discount += max_y_so_far
            
        print(initial_total_cost - total_discount)
        
    except (IOError, ValueError):
        return

solve()

算法及复杂度

  • 算法：贪心 / 排序 / 双指针

  • 时间复杂度: 。瓶颈在于对商品和优惠券数组的排序。双指针扫描部分的时间复杂度是 。

  • 空间复杂度: ，用于存储商品价格和优惠券信息。