B. 折扣 题解

一、题意理解

• $n$ 个商品，价格 $a_1, \dots, a_n$。
• $k$ 张折扣券，面值 $b_1, \dots, b_k$。
• 面值为 $x$ 的券：选 $x$ 个商品，最便宜的免费，其余 $x-1$ 个全价。
• 每个商品最多参与一张券，每张券最多用一次。
• 求购买所有商品的最小总花费。

二、核心观察

2.1 最优策略的结构

将商品按价格从大到小排序。设排序后的价格为 $c_1 \geq c_2 \geq \dots \geq c_n$。

引理 1：每张券覆盖的商品在排序后必须是连续的一段。

• 证明：如果不连续，可以将跳跃过的商品纳入，把券外的商品排除，这样免费的商品只会更便宜或不变，总花费不会增加。

引理 2：所有被券覆盖的商品构成排序后价格的一个前缀 $c_1, c_2, \dots, c_m$。

• 证明：如果有一个较贵的商品未被任何券覆盖，可以将某张券覆盖的最便宜商品换成该较贵商品，免费商品更贵，花费减少。

引理 3：在使用时，券应按面值从小到大排列，且依次覆盖前缀中的连续段。

• 证明：如果两张相邻的券，左边面值大于右边，交换它们的位置可以使更小的免费值被更短的券覆盖，从而左边的免费商品更贵，总花费减少。

2.2 最优使用的券集合

引理 4：使用的券应该是按面值排序后的一个前缀。

• 证明：如果有较大的券被使用而较小的券未被使用，可以将大券替换为小券，免费商品的位置会向左移动（即更贵的商品免费），花费减少。如果还能额外加入更小的券覆盖未被覆盖的商品，显然更优。

三、最终算法

综合以上分析，最优策略为：

1. 将商品按价格升序排列（方便从便宜的开始免费）。
2. 将折扣券按面值升序排列。
3. 所有商品的总和作为初始总花费。
4. 从最便宜的商品开始，依次使用面值最小的券：
   • 跳过 $b_i$ 个商品（即这些商品中的最便宜的那个免费），将总花费减去该商品的价格。
   • 继续处理下一张券，直到券用完或商品不够用。

四、代码实现（C++）

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

void solve() {
    int n, k;
    cin >> n >> k;
    
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    vector<int> b(k);
    for (int i = 0; i < k; i++) cin >> b[i];
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    ll ans = accumulate(a.begin(), a.end(), 0LL);
    
    int id = n;
    for (int i = 0; i < k; i++) {
        id -= b[i];
        if (id >= 0)
            ans -= a[id];
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) solve();
    
    return 0;
}

五、复杂度分析

• 排序价格：$O(n \log n)$
• 排序券：$O(k \log k)$
• 遍历券：$O(k)$
• 每个测试用例总复杂度 $O(n \log n + k \log k)$。
• $\sum n, \sum k \leq 2 \times 10^5$，完全可行。
• 空间复杂度 $O(n + k)$。