题解：P11268 【MX-S5-T2】买东西题

首先不可能按原价买。因为 $b_i \le a_i$。

我们先默认所有物品都是按折扣价 $b_i$ 买。然后尝试用优惠券让答案变小。

不难发现给物品 $i$ 使用优惠券 $j$ 后，答案会减小 $v_j-a_i+b_i$。当然前提是 $a_i \ge w_j$。我们当然是希望让这个东西的和最大。令 $c_i=a_i-b_i$，也就是希望最大化 $v_j-c_i$ 的和。

于是我们将所有物品按照 $a_i$ 降序排序。那么**能使优惠券 $j$ 有效的物品一定是一段前缀**（有效意味 $a_i \ge w_j$）。令这个前缀是 $[1, p_j]$。$p_j$ 的求解可以二分也可以 two-pointers。

于是问题变成了，对于每张优惠券 $j$，需要为它匹配一个物品 $i \le p_j$，然后获得 $v_j-c_i$ 的收益，或者不匹配。要求一个物品不能被多次匹配。求最大收益和。

我们将所有优惠券按照 $p_j$ 升序排序。然后依次考虑每张优惠券 $j$，为它匹配一个物品。

有一种朴素想法：用一个小根堆，以 $c_i$ 为关键字排序，维护 $[1, p_j]$ 中所有仍没匹配的物品 $i$。每次选择堆顶的物品，让优惠券 $j$ 和这个堆顶匹配。因为 $c_i$ 越小 $v_j-c_i$ 越大。

很显然这样是错误的。~~因为真这么简单就不是 NOIP-T2 了~~。因为如果此时把堆顶和 $j$ 匹配，而且在 $j$ 后面有一个优惠券 $k$ 满足 $v_k \ge v_j$，但是匹配到 $k$ 时堆空了（也就是不存在没匹配的物品了），那么把 $j$ 换成 $k$ 一定更优。

所以反悔贪心。

根据上面说的，枚举到一张优惠券 $j$ 时，它会有三种可能：

- 选择一个 $[1,p_j]$ 中仍未匹配的 $c$ 最小的物品 $i$。如果 $v_j \ge c_i$，则与它匹配。答案会增加 $v_j-c_i$。
- 选择一个已经匹配上的 $v$ 最小的优惠券 $k$。如果 $v_j \ge v_k$，则将 $k$ 替换成 $j$。答案会增加 $v_j-v_k$。
- 弃之。答案不变。

考虑如何维护这个过程。我们用一个小根堆，同时存储所有 $[1,p_j]$ 中仍未匹配的物品的 $c_i$，以及所有已经匹配上的优惠券的 $v_k$。可以发现前两种操作对答案的贡献都是 $v_j$ 减堆顶（即堆中的最小值）。

剩下的就是模拟了。

```cpp
#include "bits/stdc++.h"

using namespace std;

#define int long long

const int N = 1e6 + 10;

int n, m;

struct Good {
  int a, b, c;
}goods[N];

struct Quan {
  int w, v, p;
}quans[N];

signed main() {
  cin >> n >> m;

int sum = 0;
  for (int i = 1; i <= n; ++ i ) {
    cin >> goods[i].a >> goods[i].b;
    goods[i].c = goods[i].a - goods[i].b;
    sum += goods[i].b;
  }

for (int i = 1; i <= m; ++ i ) {
    cin >> quans[i].w >> quans[i].v;
  }

sort(goods + 1, goods + n + 1,
    [&](Good x, Good y) {
      return x.a > y.a;
    });
  
  for (int i = 1; i <= m; ++ i ) {
    int lo = 1, hi = n;
    while (lo <= hi) {
      int mid = lo + hi >> 1;
      if (goods[mid].a >= quans[i].w) {
        quans[i].p = mid;
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
  }

sort(quans + 1, quans + m + 1,
    [&](Quan x, Quan y) {
      return x.p < y.p;
    });
  
  priority_queue<int, vector<int>, greater<int>> pq;
  int res = 0;
  for (int i = 1, j = 1; i <= m; ++ i ) {
    while (j <= quans[i].p) {
      pq.push(goods[j].c);
      j ++ ;
    }

if (pq.size() && pq.top() < quans[i].v) {
      res += quans[i].v - pq.top();
      pq.pop();
      pq.push(quans[i].v);
    }
  }
	
  cout << sum - res;

return 0;
}
```

正在渲染内容...