题目重述

有 $n$ 只怪物，第 $i$ 只怪物的战斗力为 $a_i$。
玩家初始战斗力为 $c$，有 $k$ 只拖鞋。

两种操作：

1. 击杀：若当前怪物战斗力 $\le c$，可以击杀它，击杀后 $c$ 增加该怪物的当前战斗力。
2. 扔拖鞋：向一只活着的怪物扔一只拖鞋，使其战斗力 $+1$。

目标：通过合理安排操作顺序，最大化最终战斗力 $c$。

关键观察

1. 击杀永远是有益的：只要能击杀，就应该击杀，因为击杀会提升 $c$，让你有能力击杀更强的怪物。
2. 拖鞋的作用：给怪物扔拖鞋会增加它的战斗力，这看起来是坏事（更难击杀），但结合击杀来看：
   • 如果一只怪物当前战斗力 $a_i < c$，我们本可以直接击杀，获得 $a_i$ 的收益。
   • 但如果先用拖鞋把它提升到 $c$（需要 $c - a_i$ 只拖鞋），再击杀，就能获得 $c$ 的收益，比原来多了 $c - a_i$。
   • 所以拖鞋的本质是：用 $1$ 只拖鞋换取未来击杀时多 $1$ 点收益，但前提是你能在提升后击杀它。
3. 拖鞋的时机：给怪物扔拖鞋的最佳时机，是在即将击杀它之前。因为如果太早扔，怪物变强可能会干扰击杀顺序，而且拖鞋数量有限。
4. 击杀顺序：应该优先击杀战斗力小的怪物，因为它们容易满足条件，击杀后能提升 $c$，从而有能力处理更强的怪物。所以按怪物初始战斗力升序处理是合理的。

算法思路

将怪物按初始战斗力 $a_i$ 从小到大排序。

按顺序处理每个怪物：

• 设当前战斗力为 $C$。
• 如果当前怪物的初始战斗力 $a_i > C$：
  • 由于怪物已排序，后续怪物初始战斗力更大，不可能被击杀，直接结束。
• 如果当前怪物的初始战斗力 $a_i \le C$：
  • 我们可以用拖鞋将它提升到 $C$（如果拖鞋足够），这样击杀后 $C$ 变为 $C + C = 2C$。
  • 提升需要的拖鞋数 $= C - a_i$。
  • 实际使用的拖鞋数 $= \min(k,\ C - a_i)$，因为拖鞋可能不够。
  • 更新：$k$ 减去使用的拖鞋数，$C$ 增加 $a_i + \text{使用的拖鞋数}$。

注意：即使拖鞋不够将怪物完全提升到 $C$，我们仍然可以击杀它（因为 $a_i \le C$），只是收益少一些。

示例演示

以第六个测试用例为例：

n=5, c=18, k=30
a = [1, 2, 93, 84, 2]

排序后：$[1, 2, 2, 84, 93]$

最终 $C = 53$，与输出一致。

正确性证明

贪心选择性质：
假设当前能击杀的最小怪物是 $a_i$（$a_i \le C$），我们应该先用拖鞋提升它再击杀，而不是留给后面的怪物。
因为：

• 提升它需要 $C - a_i$ 只拖鞋，收益是让 $C$ 翻倍（从 $C$ 到 $2C$）。
• 如果留拖鞋给后面更大的怪物 $a_j$，提升它到 $C$ 需要更多拖鞋（因为 $a_j \ge a_i$，所以 $C - a_j \le C - a_i$），而击杀后的收益相同（都是 $C \to 2C$），但更早获得 $2C$ 能让你更快击杀后面的怪物。
  所以先处理小怪物是最优的。

最优子结构：
处理完前 $i$ 个怪物后，剩余问题与原问题结构相同（剩余怪物按初始顺序，新的 $C$ 和 $k$），因此贪心策略可以递归进行。

时间复杂度

• 排序：$O(n \log n)$
• 遍历处理：$O(n)$
• 总复杂度：$O(t \cdot n \log n)$，$n \le 100$，$t \le 500$，完全可行。

代码实现

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

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, k;
        long long C;
        scanf("%d %lld %d", &n, &C, &k);
        
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        
        sort(a.begin(), a.end());
        
        for (int i = 0; i < n; i++) {
            if (a[i] > C) break;  // 杀不死了
            
            int need = C - a[i];  // 提升到 C 需要的拖鞋数
            int use = min(1ll * k, 1ll * need);
            k -= use;
            C += a[i] + use;
        }
        
        printf("%lld\n", C);
    }
    return 0;
}

总结

这道题的核心是：

1. 按怪物初始战斗力升序处理。
2. 每次遇到可击杀的怪物，优先用拖鞋将其提升到当前战斗力再击杀，从而最大化收益。
3. 拖鞋不够时，能提升多少就提升多少，但无论如何都能击杀（因为初始 $a_i \le C$）。
4. 一旦遇到初始战斗力大于当前战斗力的怪物，后续都无法击杀，直接结束。