题解

题面描述

多多购物车内有$n$件商品，对于第$i$件商品价格是$p_i$元。另外多多有$m$张优惠券，每种优惠券只能用一次。第$j$张优惠券需要满$a_j$元才能使用，使用后可减免$b_j$元（且$b_j\le a_j$）。每张优惠券最多分配给一个商品，且每个商品最多使用一张优惠券。

目标是：分配优惠券到部分或全部商品上，使得总减免金额最大，并输出最大总减免值。

思路与解法

1. 排序

   • 将商品价格数组$p$按从小到大排序；
   • 将优惠券数组按照优惠券门槛$a_j$从小到大排序。

2. 贪心策略

   • 遍历每个商品，对于当前商品价格$p_i$，说明所有门槛不超过$p_i$的优惠券均可使用。
   • 将这些优惠券的优惠额度$b_j$放入最大堆中。
   • 从堆中取出$b_j$最大的优惠券分配给该商品，这样就能确保对于每个商品使用的是当前条件下最高的优惠券，从而使总减免金额最大。

3. 时间复杂度

   • 排序的时间复杂度为$O(n\log n)$和$O(m\log m)$；
   • 遍历过程中每个优惠券只入堆一次，取出堆顶的操作总共不超过$O(m\log m)$。
   • 总的时间复杂度为$O((n+m)\log m)$，可处理$n,m\le 100000$的情况。

代码分析

• 变量说明

  • 商品数量用变量$n$表示，优惠券数量用变量$m$表示。
  • 数组$p$存放商品价格；
  • 数组（或向量）$\text{coupons}$存放优惠券，存储方式为二元组$(a_j,\, b_j)$。

• 排序

  • 商品价格$p$按价格从小到大排序；
  • 优惠券按照门槛$a_j$从小到大排序以便于顺序添加到堆中。

• 堆的使用

  • 使用最大堆（优先队列），按照优惠额度$b_j$从大到小排序；
  • 对于每个商品，将所有门槛$a_j\le p_i$的优惠券加入堆中，并从堆顶取出最优的一个应用。

• 结果

  • 累加应用的优惠额度即为答案，并最终输出。

C++ 解法

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

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

    int n, m;
    cin >> n >> m; // 读取商品数量n和优惠券数量m
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i]; // 读取每个商品的价格p[i]
    }
    // 每个优惠券为一个二元组(a, b)，其中a为门槛，b为优惠额度
    vector<pair<int, int>> coupons(m);
    for(int j = 0; j < m; j++){
        cin >> coupons[j].first >> coupons[j].second; // 读取优惠券数据
    }

    // 对商品价格p按从小到大排序
    sort(p.begin(), p.end());
    // 对优惠券根据门槛a从小到大排序
    sort(coupons.begin(), coupons.end());

    ll ans = 0; // 保存最大总减免金额
    int j = 0; // 优惠券数组的下标
    // 定义最大堆，按照优惠额度b排序
    priority_queue<int> pq;
    for (int i = 0; i < n; i++){
        
        while(j < m && coupons[j].first <= p[i]){
            pq.push(coupons[j].second);
            j++;
        }
        // 如果堆非空，则取出其中优惠额度最高的优惠券并应用于当前商品
        if(!pq.empty()){
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans << "\n"; // 输出最大总减免金额
    return 0;
}

Python 解法

# 读取输入数据
n, m = map(int, input().split())  # 读取商品数量n和优惠券数量m
p = list(map(int, input().split()))  # 读取每个商品的价格p

coupons = []
for _ in range(m):
    a, b = map(int, input().split())
    coupons.append((a, b))  # 每个优惠券为二元组(a, b)

# 对商品价格p进行升序排序
p.sort()
# 对优惠券按门槛a升序排序
coupons.sort(key=lambda x: x[0])

import heapq
# Python的heapq为小根堆，因此存储负数实现最大堆
max_heap = []
ans = 0
j = 0  # 优惠券数组的下标

for price in p:
   
    while j < m and coupons[j][0] <= price:
        # 存入负的b以构造最大堆
        heapq.heappush(max_heap, -coupons[j][1])
        j += 1
    # 若堆内存在优惠券，则弹出优惠额度最大的一个
    if max_heap:
        best_discount = -heapq.heappop(max_heap)
        ans += best_discount

print(ans)  # 输出最大总减免金额

Java 解法

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        int n = Integer.parseInt(parts[0]); // 商品数量n
        int m = Integer.parseInt(parts[1]); // 优惠券数量m
        
        int[] prices = new int[n];
        parts = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            prices[i] = Integer.parseInt(parts[i]); // 读取每个商品的价格p[i]
        }
        
        // 定义优惠券数组，每个优惠券为一个二元组(a, b)
        Coupon[] coupons = new Coupon[m];
        for (int j = 0; j < m; j++) {
            parts = br.readLine().split(" ");
            int a = Integer.parseInt(parts[0]); // 门槛a
            int b = Integer.parseInt(parts[1]); // 优惠额度b
            coupons[j] = new Coupon(a, b);
        }
        
        // 对商品价格数组按升序排序
        Arrays.sort(prices);
        // 对优惠券数组根据门槛a升序排序
        Arrays.sort(coupons, new Comparator<Coupon>(){
            public int compare(Coupon c1, Coupon c2){
                return Integer.compare(c1.a, c2.a);
            }
        });
        
        // 使用PriorityQueue构造最大堆，按照b降序排序
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        long ans = 0;  // 保存最大总减免金额
        int j = 0;  // 优惠券数组的下标
        
        // 遍历每个商品价格
        for (int price : prices) {
            
            while(j < m && coupons[j].a <= price) {
                pq.add(coupons[j].b);
                j++;
            }
            // 如果堆不为空，则取出优惠额度最大的优惠券分配给当前商品
            if (!pq.isEmpty()) {
                ans += pq.poll();
            }
        }
        
        System.out.println(ans); // 输出最大总减免金额
    }
    
    // 定义Coupon类存储优惠券信息
    static class Coupon {
        int a; // 门槛a
        int b; // 优惠额度b
        Coupon(int a, int b) {
            this.a = a;
            this.b = b;
        }
    }
}

题目内容

多多购物车内有$n$件商品，对于第$i$件商品价格是$p_i$元。另外多多有$m$张优惠券，每种优惠券只能用一次。第$j$张优惠券需要满$a_j$元才能使用，使用后可减免$b_j$元$(b_j<=a_j)$。每张优惠券最多分配给一个商品，且每个商品最多使用一张优惠券。

多多想购买购物车所有的商品，请设计一种优惠券分配方案，使得总减免金额最大，并输出最大总减免。

输入描述

第一行包含两个整数n和m，分别表示商品数量和优惠券数量。$(1≤n,m≤100000)$

第二行包含$n$个整数$p_1$,$p_2$,...$p_n$表示各商品的价格$(1≤p_j≤100000)$

接下来m行，每行两个整数$a_j,b_j$表示第$j$张优惠券的门槛和减免金额$(1≤b_j≤a_j≤100000)$

输出描述

一个整数,表示最大总减免金额

样例1

输入

3 2
15 20 25
20 5
25 8

输出

13

说明

满$20$减$5$的优惠券分配给价格$15$的商品，满$25$减$8$的优惠券分配给价格25的商品，一共减免$13$元。

样例2

输入

2 2
10 20
15 3
20 4

输出

4