F. Shovels Shop 解题思路 ​

核心问题分析 ​

题意其实就是个“凑单薅羊毛”的故事：商店里有 $n$ 把铲子，第 $i$ 把价格 $a_i$。Misha 必须恰好买 $k$ 把，可以分很多次结账。每次结账时他挑出一堆还没买的铲子一起付钱。

商店有 $m$ 个优惠 $(x_j, y_j)$：如果某一次结账恰好买了 $x_j$ 把，那么这堆里最便宜的 $y_j$ 把免费。每次结账最多用一个优惠（也可以不用），同一个优惠可以反复使用。问买齐 $k$ 把的最小花费。

数据范围给得很有意思：$n, m \le 2 \times 10^5$，但 $k \le \min(n, 2000)$。这个 $2000$ 就是在向我们招手——它在暗示一个 $O(k^2)$ 量级的算法。我们先做两步显而易见但很关键的“化简”，把这道看起来吓人的题压扁。

1. 第一刀：根本不用碰那些贵铲子 ​

我们要买恰好 $k$ 把，目标是总花费最小。那还用想吗？当然是从最便宜的 $k$ 把里挑。直观地说：如果你的方案里买了某把贵铲子 $p$，却放着一把更便宜、还没买的铲子 $q$ 不要，那把 $p$ 换成 $q$ 一定不亏——因为不管 $p$ 在它那次结账里是付费还是被免，换成更便宜的 $q$ 都只会让那一份钱变小或持平。

所以代码上来就两件事：整体排序，然后只取最便宜的 $k$ 把做前缀和。

sort(all(a));
vector<int> pref(k + 1);
for (int i = 1; i <= k; i++) pref[i] = pref[i - 1] + a[i];

注意 a 开的是 $n+1$ 长度、下标从 $1$ 用起，而 a[0] 是默认的 $0$。升序排完之后 a[0]=0 待在最前面（它最小嘛），紧跟着的 a[1], a[2], \dots, a[k] 正好就是从便宜到贵排好的前 $k$ 把铲子。pref[i] 就是这 $k$ 把里最便宜的前 $i$ 把之和。剩下那 $n-k$ 把贵铲子，从此跟我们再无瓜葛。

2. 第二刀：把 $m$ 个优惠压成一张“尺寸表” ​

优惠有 $2 \times 10^5$ 个，但本质上一个优惠只由“买几把”这个尺寸 $x$ 来索引。对于固定的尺寸 $x$，我们当然只关心能白嫖最多的那个 $y$——免得越多越好嘛。而且一次结账最多买 $k$ 把（我们总共才买 $k$ 把），所有 $x > k$ 的优惠直接扔掉。

for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    if (x > k) continue;
    b[x] = max(b[x], y);
}

于是 $b[j]$ 的含义就钉死了：“某次结账恰好买 $j$ 把”时，能免费拿走的最多铲子数。没有对应优惠的尺寸，$b[j]$ 就是 $0$（一把都不免，全价照付）。这一步把 $m$ 个优惠彻底压缩成了一张长度 $k+1$ 的小表。

3. 灵魂观察：免费的，永远是最贵的那批留给最便宜的那批 ​

这是整道题最妙的地方。我们已经锁定要买“最便宜的 $k$ 把”，现在的问题是怎么把它们切成若干次结账，让总免费金额最大（等价于花费最小）。

关键结论是：

把这 $k$ 把铲子按价格从便宜到贵排好，最优方案一定可以让每一次结账都拿走“当前剩下里最便宜的一段连续前缀”，并且在那一段里被免掉的，正好是这一段里最便宜的几把。

换句话说，整体最便宜的那几把铲子，会被安排成各次结账里的“免费名额”。为什么？因为优惠免的永远是“本次结账里最便宜的 $y$ 把”，那我们就该让全局最便宜的铲子去当这个免费名额——白嫖就要白嫖最该省的钱才划算（其实这里反着想更顺：付费的应该尽量是便宜的？不对，是免费的要尽量贵……）。

我们正经地捋一遍代码到底是怎么算的，结论会自动浮出来。设我们要决定最便宜的前 $i$ 把怎么买光，记 $dp[i]$ 为买下这前 $i$ 把的最小花费。考虑最后一次结账买了 $j$ 把（$1 \le j \le i$），那么这次结账买的就是前 $i$ 把里最贵的 $j$ 把，也就是下标区间 $[\,i-j+1,\ i\,]$ 这一段；而前面 $i-j$ 把留给之前的结账，花费是 $dp[i-j]$。

这一次结账买了 $j$ 把，可以套用 $b[j]$ 这个优惠，免掉这次里最便宜的 $b[j]$ 把——也就是这一段 $[\,i-j+1,\ i\,]$ 里最靠前（最便宜）的那 $b[j]$ 把，下标区间 $[\,i-j+1,\ i-j+b[j]\,]$。于是这次结账实际付的钱是：

$$\big(\text{这一段的总价}\big) - \big(\text{免掉的前 } b[j] \text{ 把}\big) = \big(pref[i] - pref[i-j]\big) - \big(pref[i-j+b[j]] - pref[i-j]\big)$$

把它整理一下，那两个 $pref[i-j]$ 直接消掉了，付费部分干净利落地变成：

$$pref[i] - pref[i-j+b[j]] = pref[i] - pref\big(i-j-b[j]\big)$$

是不是和代码里那一行严丝合缝？

dp[i] = min(dp[i], dp[i - j] + pref[i] - pref[i - (j - b[j])]);

直观解读就是：这一段里最便宜的 $b[j]$ 把免费，剩下 $j - b[j]$ 把（也就是这一段里最贵的那些）全价付。而因为我们是按“便宜在前”铺开做 dp 的，所有结账拼起来恰好把全局最便宜的铲子都吃成了免费名额——前面那个绕来绕去的结论，到这里就被代码自动实现了，一点都不用我们操心。

4. 把 DP 跑起来 ​

状态和转移都到位了，剩下就是无脑填表：

vector<int> dp(k + 1, 2e18);
dp[0] = 0;
for (int i = 1; i <= k; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] = min(dp[i], dp[i - j] + pref[i] - pref[i - (j - b[j])]);
    }
}
cout << dp[k] << endl;

• $dp[0] = 0$：一把不买，零花费，天经地义的起点。
• 外层枚举“已经处理掉最便宜的前 $i$ 把”，内层枚举“最后一次结账买 $j$ 把”。
• 当 $b[j] = 0$（这个尺寸没优惠）时，转移退化成 $dp[i-j] + pref[i] - pref[i-j]$，也就是这 $j$ 把原价照单全收——把“不用任何优惠”这种情况自然地包含进来了，不用单独写。

最后 $dp[k]$ 就是买齐 $k$ 把的最小花费。两层循环都到 $k$，复杂度是漂亮的

$$O(k^2)$$

$2000^2 = 4 \times 10^6$，2 秒时限里轻松起飞。前面读入和排序是 $O(n \log n + m)$，丝毫不影响。一道挂着 $2 \times 10^5$ 大数据范围吓人、实则被 $k \le 2000$ 一句话锁死成 $O(k^2)$ 小 DP 的好题，就这么收工啦。

CPP 代码实现 ​

// F. Shovels Shop

#include <bits/stdc++.h>
#define lg(x) (63 - __builtin_clzll(x))
#define all(x) (x).begin(), (x).end()
#define low_bit(x) ((x) & (-x))
#define pb push_back
#define db long double
#define int long long
#define sz(x) (int)x.size()
#define endl "\n"

using namespace std;

void solve() {

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n + 1);
    vector<int> b(k + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (x > k) continue;
        b[x] = max(b[x], y);
    }
    sort(all(a));
    vector<int> pref(k + 1);
    for (int i = 1; i <= k; i++) pref[i] = pref[i - 1] + a[i];
    vector<int> dp(k + 1, 2e18);
    dp[0] = 0;
    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j] + pref[i] - pref[i - (j - b[j])]);
        }
    }
    cout << dp[k] << endl;
    
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    
    while (t--) {
        solve();
    }
    
}