E - One Time Coupon

思路

每种商品至少买一件，我们可以将总花费拆分为：

• 选若干商品原价买（获得优惠券）
• 剩余商品券价买（消耗优惠券）
• 额外原价重复购买最便宜的商品来补足优惠券

我们先设定：

• $res = \sum_{i=1}^{n} B_i$：假设所有商品都用券价买的基准成本
• $k$：额外用原价购买最便宜商品的次数（获得 $k$ 张优惠券）
• $s$：选择用原价购买的不同商品数量

总券数 = $k + s$（$k$ 次额外购买 + $s$ 个商品原价购买各产 1 张券） 需要券价买的商品数 = $n - s$（$s$ 个商品原价买了，剩下 $n-s$ 个用券价）

定义域：$2s + k \geq n \Rightarrow s \geq \left\lceil \frac{n - k}{2} \right\rceil$

总成本公式：

$$\text{cost} = \sum_{i=1}^{n} B_i + \underbrace{\sum_{i \in S} (A_i - B_i)}_{\text{原价差价}} + \underbrace{k \cdot \min A}_{\text{额外购品成本}}$$

对于固定的 $s$，要让 $\sum_{i \in S} (A_i - B_i)$ 最小，贪心选择 $A_i - B_i$ 最小的 $s$ 个商品即可。

枚举 $k \in [0, n]$，令 $s = \left\lceil \frac{n - k}{2} \right\rceil$，通过排序 + 前缀和快速计算答案。

复杂度

排序 $O(n \log n)$，枚举 $O(n)$，总复杂度 $O(n \log n)$。

代码

答案 $\ge \sum_{i=1}^{n} B_i$，最坏为 $2 \times 10^5 \times 10^9 = 2 \times 10^{14}$，需要 long long。

// E - One Time Coupon
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5 + 1023;
int t, n, a[N], b[N], dif[N];
long long sum[N];

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        long long ans = 1e18, res = 0;
        int minv = 1e9;
        for (int i = 1; i <= n; i++) {
            cin >> a[i] >> b[i];
            dif[i] = a[i] - b[i];
            res += b[i];
            minv = min(minv, a[i]);
        }
        sort(dif + 1, dif + n + 1);
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + dif[i];
        for (int k = 0; k <= n; k++)
            ans = min(ans, res + sum[max(0, n - k + 1 >> 1)] + 1ll * k * minv);
        cout << ans << '\n';
    }
    return 0;
}