题解：B4071 [GESP202412 五级] 武器强化

· · 题解

本题解注重以下 3 个问题：

  1. 本题的基本思路是什么
  2. 解题的逻辑和步骤
  3. 更多的启发

基本思路

本题的对于贪心来说，最大的困扰是：你究竟是选择最低价的配件来转换，还是选择那些拥有最多配件的其他武器来转换。选择最低价的好处当然是成本低，但优先选择目前排名最高的武器的配件，一方面增加了自己，一方面可以打击对手，有双重的好处。

看似这里应该做一个动态规划，但是复杂度太高，仍然应该用贪心的思路来做。贪心题的一般解法步骤是：

  1. 把问题分解为若干步
  2. 每步选择一个局部最优的方案
  3. 把这些方案合并期望得到全局最优解

分解步骤是最关键的，如果这道题你把步骤分解为每次选择一个配件，让后看怎样找到最合适的配件，这就无法成功（由于上面的困扰）。

正确的做法是进行多轮游戏：在每轮游戏中使用不同的策略，最后在所有策略中找到一个最好的策略。下面展开说明一下策略的设计。

解题的逻辑和步骤

这里的重点多轮游戏怎么设计，用了一种反向思维，从结果倒推过程。回答两个问题：即 1 号武器赢的时候究竟拥有多少配件？它究竟是怎样赢的？

首先， 1 号武器必须超过所有其他武器，因为配件总数是m，所以 1 号最多占有 m/2+1 个配件就可以绝对胜利。最少也必须占有 1 个配件才可能胜利（其他都是 0 ）。所以第一个问题就有了范围。

现在，看它是怎么赢的。假设 1 号武器赢的时候拥有 x 个配件，那么所有武器最多保留 x-1 个配件，超过这个数量的最便宜的那部分配件肯定是被转换了，这个费用是必须付的，无论价格高低。如果 1 号武器转换了这些配件还不够 x 个，可以自由地从剩下的配件中进行最低价选择。这就解决了上面说的两难困扰。

具体做法如下就是枚举所有赢时的配件数量，然后用上面说的这个逻辑去倒推计算实际的费用。最后在所有情况中选择一个费用最低的方案。我们同时得到了最低费用和此时的 1 号武器配件数。

更多的启发

当明确了取胜的配件数量时，这个具体的计算过程，确实的贪心。但实际上获得最优解靠的不是贪心而是枚举。 如果数量特别大，还可以用二分。

贪心关注的是局部，但最优解必然事实上是全局最优的。所以我们的解法中，必然会在某个角度反映出全局的考虑。这种贪心+枚举（或二分）的技巧在实际题目中还是比较经常出现的。

AC 代码如下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
vector<int> cs[1003];
// 计算费用的核心函数
ll calc(int aim) {
    int cur_cnt = cs[1].size();
    ll res = 0;
    vector<int> tmp;  // 备选配件库
    // 首先，从2号开始，每种武器超过aim-1的部分，全部转换，必不可少的费用
    for (int i = 2; i<=n; i++) {
        int buy = max((int)cs[i].size() - aim + 1, 0); 
        for (int j = 0; j < buy; j++) {
            res += cs[i][j];
        }
        cur_cnt += buy;
        // 剩下的配件，进入配件库备选
        for (int j = buy; j < cs[i].size(); ++j) {
            tmp.push_back(cs[i][j]);
        }
    }
    sort(tmp.begin(), tmp.end());  // 备选配件库排序
    // 收了所有武器的超标配件后，1号可能仍然达不到获胜标准，再选最低价
    for (int i = 0; i < aim - cur_cnt; i++) {
        res += tmp[i];
    }
    return res;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <=m; i++) {
        int p, c;
        cin >> p >> c;
        cs[p].push_back(c);
    }
    // 每种武器的配件按费用排序，因为会从最低价格开始使用
    for (int i = 1; i <=n; i++) {
        sort(cs[i].begin(), cs[i].end());
    }
    ll ans = 1e18;
    // 遍历1号武器胜利时的数量，并计算费用
    for (int i = 1; i <= m/2+1; i++) {
        ll x= calc(i);
        ans = min(ans, x);
    }
    cout << ans;
}