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

· · 题解

原题

题目大意

有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第 p_i 种武器，小杨可以花费 c_i 金币将该材料对应的适配武器修改为任意武器。小杨最喜欢第 1 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

解法

假设结果为 ans。

可以用数组 cs_{p} 表示适配第 p 种武器的所有材料花费，然后用 cnt_i 表示共有 cnt_i 适配第 p 种武器的材料，你也可以理解为 cs_p 的长度。

随后，开贪，既然要求最少花费，那么就将 cs_p 小的排在前，极易证明，如果不把 cs_p 小的排在前，求花费时加不到 cs_{p,min}（cs_p 中最小值），花费就不是最小的。

排序后，核心来了。定义 i 为遍历 m 种强化材料的循环变量。因为题面有：

小杨最喜欢第 1 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨

计算为了满足该条件最少需要花费多少金币。

所以我们尽量使用 cnt 中材料多的，cs_{1\cdots cnt_i} 中最便宜的材料，使用这种材料将第 i 种武器改成第 1 种武器，随后 ans 判断当前花费和 ans 取最小值，即 ans\gets \min(ans,当前花费)。

如何算当前花费呢？先令 curcnt\gets cnt_1,res\gets 0（res 表示当前花费）并定义数组 tmp 表示最便宜的材料有那些。因为要让第 1 种武器适配该武器的强化材料种类数尽可能多，必然会产生一个单调上升序列：\left \{ 1,2,3,4,\cdots \right \} 。假设 ii 指序列中的数（对应代码中 f 函数的形参），如果 cnt_i-ii+1 是负数，说明 cs_i 中的长度比 ii 短，如果比 ii 长，res 加上花费即可。

假设 b 是 cs_i 中减去 ii 加一的长度，然后将 cs_i 的数值加入到 tmp 中。curcnt 指的是 tmp 的长度，所以每轮循环 curcnt\gets curcnt+b。但是如果 cnt_i-ii+1 是负数，curcnt 就小了，所以 b\gets \min(cnt_i-ii+1,0)。

最后对 tmp 进行排序，res 加上 tmp 前 ii-curcnt 个数，然后 ans 和 res 进行比较 ans 取小的。

最后开 long long 就行了。

代码

#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int maxm=1001,maxn=maxm;
long long n,m,p[maxn],c[maxm];
long long cnt[maxn];
vector<int> cs[maxn];
long long ans=1e18;
long long f(int ii){
    long long curcnt=cnt[1],res=0;
    vector<int> tmp;
    for(int i=2;i<=n;i++){
        int b=max((int)(cs[i].size()-ii+1),0);
        for(int j=0;j<b;j++){
            res+=cs[i][j];
        }
        curcnt+=b;
        for(int j=b;j<cs[i].size();j++){
            tmp.push_back(cs[i][j]);
        }
    }
    sort(tmp.begin(),tmp.end());
    for(int i=0;i<ii-curcnt;i++){
        res+=tmp[i];
    }
    return res;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>p[i]>>c[i];
        cnt[p[i]]++;
        cs[p[i]].push_back(c[i]);
    }
    for(int i=1;i<=n;i++){
        sort(cs[i].begin(),cs[i].end());
    }
    for(int i=max((long long)(cnt[1]),1ll);i<=m;i++){//注意范围！
        ans=min(ans,f(i));
    }
    cout<<ans<<endl;
    return 0;
}