题目重述

有 $n$ 个物品，第 $i$ 个物品的价格为 $a_i$。Alice 和 Bob 轮流拿物品，Alice 先手，每人每次拿一个，直到拿完。
设 $A$ 为 Alice 拿的物品总价，$B$ 为 Bob 拿的物品总价，得分为 $A - B$。Alice 想最大化得分，Bob 想最小化得分，两人都采取最优策略。

在游戏开始前，Bob 可以增加若干物品的价格（只能增加，不能减少），总增加量不超过 $k$。
问：Bob 通过最优的修改和最优的游戏策略，能实现的最小可能得分是多少？

---

第一步：确定不修改时的最优策略

这是一个经典的轮流取物博弈。
因为 Alice 想最大化 $A - B$，Bob 想最小化 $A - B$，且两人都能看到所有物品的价格，最优策略是每次取当前最大的物品。

证明思路：

• 考虑任意一步，轮到某玩家时，如果他拿的不是最大的，对方下一步可以拿走最大的，这对当前玩家不利。
• 因此，双方都会贪心地拿当前最大值。

所以，将价格按降序排序后，物品顺序为：

$$b_0 \ge b_1 \ge b_2 \ge \dots \ge b_{n-1}$$

那么：

• Alice 拿 $b_0, b_2, b_4, \dots$（下标为偶数的物品）
• Bob 拿 $b_1, b_3, b_5, \dots$（下标为奇数的物品）

初始得分（不修改时）为：

$$S_0 = \sum_{i=0}^{\lfloor (n-1)/2 \rfloor} b_{2i} \;-\; \sum_{i=0}^{\lfloor (n-2)/2 \rfloor} b_{2i+1} $$

---

第二步：Bob 修改的影响

Bob 只能增加物品的价格。
如果他增加的是 Alice 会拿的物品，那么 $A$ 增加，得分 $A-B$ 增加，对他不利。
所以 Bob 只会增加自己会拿的物品（即奇数下标 $b_1, b_3, \dots$）。

设 Bob 将某个自己拿的物品 $b_{2i+1}$ 增加 $x$（$x \ge 0$），则 $B$ 增加 $x$，得分 $A-B$ 减少 $x$。
因此，Bob 每增加 $1$ 单位价格到自己的物品上，得分就减少 $1$。
他的目标是在总增加量 $\le k$ 的前提下，尽可能多地减少得分。

---

第三步：Bob 能增加的极限

Bob 不能无限制地增加自己的物品，因为增加太多可能超过前一个 Alice 拿的物品，这不会带来额外的好处吗？
注意：如果 $b_{2i+1}$ 增加到超过 $b_{2i}$，那么排序顺序会改变，后续的分配也会改变。但游戏是在修改后的价格上进行的，双方仍会按降序贪心取。

关键结论：Bob 增加自己的物品，最多只能增加到等于前一个 Alice 物品的价格（即 $b_{2i}$），因为：

• 如果 $b_{2i+1} < b_{2i}$，增加它直到 $b_{2i}$ 是有效的，每增加 $1$ 减少得分 $1$。
• 如果 $b_{2i+1} \ge b_{2i}$，再增加只会让自己物品超过前面的，但排序后它可能会跑到前面去，成为 Alice 拿的？这需要分析。

实际上，更严谨的推导（官方题解）表明：
Bob 最多能让每个自己的物品 $b_{2i+1}$ 增加到 $\max(b_{2i}, b_{2i+1})$，但超过 $b_{2i}$ 没有意义，因为如果 $b_{2i+1} > b_{2i}$，那么排序后 $b_{2i+1}$ 会跑到 $b_{2i}$ 前面，导致 Alice 拿这个更大的，反而更糟。
所以 Bob 只会增加自己物品到不超过前一个 Alice 物品的价格。

因此，对于每个 $i$（$0 \le i \le \lfloor (n-2)/2 \rfloor$），Bob 能从这个物品上获得的最大减少量为：

$$d_i = \max(0,\; b_{2i} - b_{2i+1})$$

---

第四步：分配 $k$

Bob 的总减少量不能超过 $\sum d_i$，也不能超过 $k$。
因为每增加 $1$ 单位到任意自己物品上，得分就减少 $1$，且收益相同，所以 Bob 可以任意分配 $k$ 到这些 $d_i$ 上，只要不超过各自的 $d_i$。

因此，Bob 能实现的最大减少量为：

$$R = \min\left(k,\; \sum_{i=0}^{\lfloor (n-2)/2 \rfloor} \max(0,\; b_{2i} - b_{2i+1})\right) $$

---

第五步：最终答案

初始得分为 $S_0$，Bob 能减少 $R$，因此最终得分为：

$$\text{ans} = S_0 - R$$

---

第六步：算法步骤

1. 将数组 $a$ 按降序排序，得到 $b_0 \ge b_1 \ge \dots \ge b_{n-1}$。
2. 计算初始得分：$$S_0 = \sum_{i=0}^{\lfloor (n-1)/2 \rfloor} b_{2i} - \sum_{i=0}^{\lfloor (n-2)/2 \rfloor} b_{2i+1} $$
3. 计算可减少总量：$$\text{can\_reduce} = \sum_{i=0}^{\lfloor (n-2)/2 \rfloor} \max(0,\; b_{2i} - b_{2i+1}) $$
4. 实际减少量：$$R = \min(k,\; \text{can\_reduce})$$
5. 输出：$$\text{ans} = S_0 - R$$

---

第七步：验证样例

样例1

$n=2, k=5, a=[1,10]$
排序：$[10,1]$
$S_0 = 10 - 1 = 9$
$d_0 = \max(0, 10-1) = 9$
$R = \min(5,9) = 5$
$ans = 9 - 5 = 4$ ✅

样例2

$n=3, k=0, a=[10,15,12]$
排序：$[15,12,10]$
$S_0 = (15+10) - 12 = 13$
$d_0 = \max(0, 15-12) = 3$（只有 $i=0$，因为 $\lfloor (3-2)/2 \rfloor = 0$）
$R = \min(0,3) = 0$
$ans = 13$ ✅

样例3

$n=4, k=6, a=[3,1,2,4]$
排序：$[4,3,2,1]$
$S_0 = (4+2) - (3+1) = 2$
$d_0 = \max(0,4-3)=1$
$d_1 = \max(0,2-1)=1$
$\sum d = 2$
$R = \min(6,2)=2$
$ans = 2-2 = 0$ ✅

样例4

$n=2, k=4, a=[6,9]$
排序：$[9,6]$
$S_0 = 9-6=3$
$d_0 = \max(0,9-6)=3$
$R = \min(4,3)=3$
$ans = 0$ ✅

---

第八步：最终代码（标程）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        long long k;
        cin >> n >> k;
        
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        
        // 降序排序
        sort(a.rbegin(), a.rend());
        
        // 计算初始得分
        long long score = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                score += a[i];
            } else {
                score -= a[i];
            }
        }
        
        // 计算 Bob 能获得的最大减少量
        long long can_reduce = 0;
        for (int i = 1; i < n; i += 2) {
            can_reduce += max(0LL, a[i-1] - a[i]);
        }
        
        long long reduce = min(k, can_reduce);
        score -= reduce;
        
        cout << score << "\n";
    }
    
    return 0;
}

---

复杂度分析

• 排序 $O(n \log n)$，所有测试用例总和 $O(\sum n \log n) \le O(2\times10^5 \log 2\times10^5)$。
• 空间复杂度 $O(n)$。