4663: 【GESP2412五级】武器强化

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：2 解决：2

题目描述



输入

第一行包含两个正整数 ，含义如题面所示。

之后  行，每行包含两个正整数 ，代表第  种强化材料的适配武器和修改花费。


输出

输出一个整数，代表能够使适配第  种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。

样例输入 复制 

4 4
1 1
2 1
3 1
3 2

样例输出 复制 

1

提示

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m;
int cnt[1010];
vector < int > cs[1010];
ll calc(int aim) {
    int cur_cnt = cnt[1];
    ll res = 0;
    vector < int > tmp;
    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 += (ll) 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());
    for (int i = 0; i < aim - cur_cnt; i++) {
        res += (ll) tmp[i];
    }
    return res;
}
signed main() {
    // freopen("06.in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int p, c;
        cin >> p >> c;
        cnt[p]++;
        cs[p].push_back(c);
    }
    for (int i = 1; i <= n; i++) {
        sort(cs[i].begin(), cs[i].end());
    }
    ll ans = 1e18;
    for (int i = max(cnt[1], 1); i <= m; ++i) {
        ans = min(ans, calc(i));
    }
    cout << ans << "\n";
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> init_cnt(n + 1, 0);
    vector<vector<long long>> costs(n + 1);

    for (int i = 0; i < m; ++i) {
        int p, c;
        cin >> p >> c;
        init_cnt[p]++;
        if (p != 1) {
            costs[p].push_back(c);
        }
    }

    // 对每种武器 j 的花费排序
    for (int j = 2; j <= n; ++j) {
        sort(costs[j].begin(), costs[j].end());
    }

    long long ans = LLONG_MAX;
    int c1 = init_cnt[1];

    // 枚举最终武器1的数量
    for (int target = c1; target <= m + c1; ++target) {
        long long total_cost = 0;
        bool ok = true;
        int added = 0; // 需要从别的武器转移到1的数量

        for (int j = 2; j <= n; ++j) {
            // 为了让最终 cnt[j] < target
            int need = max(0, init_cnt[j] - (target - 1));
            if (need > costs[j].size()) {
                ok = false;
                break;
            }
            for (int k = 0; k < need; ++k) {
                total_cost += costs[j][k];
            }
            added += need;
        }

        // 还要保证最终 cnt[1] = c1 + added == target
        if (!ok || c1 + added != target) {
            continue;
        }

        ans = min(ans, total_cost);
    }

    cout << ans << endl;

    return 0;
}

来源/分类

提交提交记录统计露一手!