G5012 [GESP202412 五级] 武器强化 题解

知识点：枚举目标、排序、贪心。

解题思路

枚举最终第一类武器数量target。其他每类必须降到target-1及以下，先购买其最便宜的必要数量；仍不足target时，再从全部可选剩余项目中买最便宜的。

为什么正确

固定target后，每类必要购买数是硬下界，取该类最便宜者最优；补足总数无类别限制，可全局取最低费用。

易错点

第一类必须严格多于其他各类；已经属于第一类的武器免费计入have。

复杂度

时间O(m² log m+n m)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<long long>>a(n+1);
    for(int i=0;i<m;i++) {
        int p;
        long long c;
        cin>>p>>c;
        a[p].push_back(c);
    }
    for(auto &v:a)sort(v.begin(),v.end());
    long long ans=LLONG_MAX;
    for(int target=max(1,(int)a[1].size());target<=m;target++) {
        long long cost=0;
        int have=a[1].size();
        vector<long long>extra;
        for(int i=2;i<=n;i++) {
            int take=max(0,(int)a[i].size()-target+1);
            for(int j=0;j<(int)a[i].size();j++)if(j<take) {
                cost+=a[i][j];
                have++;
            }
            else extra.push_back(a[i][j]);
        }
        sort(extra.begin(),extra.end());
        for(int i=0;have<target&&i<(int)extra.size();i++,have++)cost+=extra[i];
        if(have>=target)ans=min(ans,cost);
    }
    cout<<(ans==LLONG_MAX?0:ans);
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。