企业官网建设流程全解析

描述

小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第 pi​ 种武器，小杨可以花费 ci​ 金币将该材料对应的适配武器修改为任意武器。

小杨最喜欢第 1 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

输入描述

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

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

输出描述

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

样例输入 1

4 4 1 1 2 1 3 1 3 2

样例输出 1

1

提示

解题思路

本题的核心是让适配第 1 种武器的强化材料数量严格大于其他任意武器。初始时，每种武器都有一定数量的强化材料适配，其中第 1 种武器有 cnt[1] 个。为了让第 1 种武器胜出，我们需要把其他武器的强化材料改配到第 1 种武器上，同时也要考虑把原本适配第 1 种武器的材料改走的情况（但通常不会这样做，因为这会增加第 1 种武器的数量成本）。

一个直观的贪心策略是：枚举最终第 1 种武器拥有的强化材料数量 x，要求 x 严格大于其他所有武器的数量。对于每个武器 i（i > 1），如果它当前的材料数量 cnt[i] 大于等于 x，那么必须把其中 cnt[i] - x + 1 个材料改配到第 1 种武器上，花费为这些材料中修改费用最小的若干项之和。如果所有其他武器都满足数量小于 x，则第 1 种武器还需要从剩余材料中补充到 x 个，选择费用最小的材料进行补充。

由于 n 和 m 最大均为 1000，枚举 x 的范围为 1 到 m，每次枚举需要 O(m log m) 的排序或堆操作，总复杂度 O(m^2 log m)，在数据范围内可以接受。

参考代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int n, m; cin >> n >> m; vector<int> p(m), c(m); vector<vector<int>> cost(n + 1); for (int i = 0; i < m; i++) { cin >> p[i] >> c[i]; cost[p[i]].push_back(c[i]); } for (int i = 1; i <= n; i++) { sort(cost[i].begin(), cost[i].end()); } ll ans = LLONG_MAX; for (int x = 1; x <= m; x++) { ll cur = 0; vector<int> rest; for (int i = 2; i <= n; i++) { int sz = cost[i].size(); if (sz >= x) { for (int j = 0; j < sz - x + 1; j++) { cur += cost[i][j]; } for (int j = sz - x + 1; j < sz; j++) { rest.push_back(cost[i][j]); } } else { for (int j = 0; j < sz; j++) { rest.push_back(cost[i][j]); } } } int need = x - cost[1].size(); if (need > 0) { if ((int)rest.size() < need) continue; sort(rest.begin(), rest.end()); for (int j = 0; j < need; j++) { cur += rest[j]; } } ans = min(ans, cur); } cout << ans << endl; return 0; }

复杂度分析

时间复杂度为 O(m^2 log m)，其中对每种武器内部排序的复杂度为 O(m log m)，枚举 x 的循环中每次需要 O(m log m) 的排序操作。空间复杂度为 O(n + m)，用于存储每种武器的材料费用。

数据范围与提示

对于 100% 的数据，保证 1≤n,m≤1000，1≤pi​≤n，1≤ci​≤109。

样例解释

花费 1，将第三种强化材料的适配武器由 3 改为 1。此时，武器 1 有 2 种强化材料适配，武器 2 和武器 3 都各有 1 种强化材料适配，满足适配第 1 种武器的强化材料种类数严格大于其他的武器。