洛谷B4071 [GESP202412 五级] 武器强化

题目传送门！

思路

我愿称之为gesp5史上最难想。。。

做法：贪心+模拟（or二分）

对于贪心算法来说，最最最无法理解的地方：选择价格最低的配件来转换，还是选择拥有最多配件的其他武器来转换。

选低价的好处是成本低，这个不用说。但选择目前排名最高武器的配件，好处很多，一个是增强自己，还有就是打击对手。

看似这里应该做一个动态规划

但是复杂度实在是太高

所以就想到了应该用贪心的思路来做。

回顾贪心题的基本做法

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

分解是最关键的！

正解的做法是进行多轮的游戏：在每轮游戏中使用不一样的策略，最后在所有策略中找到一个最好的。

步骤，逻辑

重点来喽！多轮游戏怎么设计

这里用了一种反向思维，从结果倒推过程。

那么 1 号武器赢的时候到底有多少配件？它是怎么赢的？

首先， 1 号武器必须超过所有其他武器，注意，必须是所有！

已知配件总数是m，所以 1 号最多占 m/2+1 个配件就绝对可以胜利。

最少也必须占有 1 个配件才可能胜利（但是其他都必须是 0 ）。。

然后再来看它是怎么赢的。

假设 1 号武器赢的时候拥有 x 个配件，那么所有武器最多保留 x−1 个配件，超过这个数量的最便宜的那部分配件肯定是被转换了!

这个费用是必须付的，不管贵不贵，因为真的对于取胜很重要。

如果 1 号武器转换了这些配件还不够 x 个的话，就可以自由地从剩下的配件中进行最低价格选择。

所以这样就可以解决上面的问题！

做法：枚举所有赢时的配件数量，然后用这个逻辑去倒推计算实际的费用。

最后选一个费用最低的方案。

这样就同时得到了费用最低的方案和 1 号武器配件数。

一些复盘启发。。

如果已经明确了取胜的数量，那就是一个纯粹的贪心。

但实际上来看，找出最优解靠的不是贪心，而是枚举！

那么数量特别大的时候，还可以用上二分！

贪心关注的是局部，局部最优解导致全局最优解。

重点：看似动态规划，实则贪心+枚举（or二分）

最后附上一个小警告：最小值要达到1e18,还有这个题优先队列做40pts

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n, m;
vector<int> a[1010];
ll all(int aim)
{
    int cnt = a[1].size();
    ll res = 0;
    vector<int> tmp;  
    for (int i = 2; i<=n; i++)
	{
        int buy = max((int)a[i].size() - aim + 1, 0);
        for (int j = 0; j < buy; j++)
		{
            res += a[i][j];
        }
        cnt += buy;
        for (int j = buy; j < a[i].size(); j++)
		{
            tmp.push_back(a[i][j]);
        }
    }
    sort(tmp.begin(), tmp.end()); 
    for (int i = 0; i < aim - 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;
        a[p].push_back(c);
    }
    for (int i = 1; i <=n; i++)
	{
        sort(a[i].begin(), a[i].end());
    }
    ll ans = 1e18;
    for (int i = 1; i <= m/2+1; i++)
	{
    	ll x= all(i);
		ans = min(ans, x);
	}
	cout << ans;
	return 0;
}

完结撒花！