描述小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第 pi 种武器小杨可以花费 ci 金币将该材料对应的适配武器修改为任意武器。小杨最喜欢第 1 种武器因此他希望适配该武器的强化材料种类数严格大于其他的武器请你帮小杨计算为了满足该条件最少需要花费多少金币。输入描述第一行包含两个正整数 n,m含义如题面所示。之后 m 行每行包含两个正整数 pi,ci代表第 i 种强化材料的适配武器和修改花费。输出描述输出一个整数代表能够使适配第 1 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。样例输入 14 4 1 1 2 1 3 1 3 2样例输出 11提示解题思路本题的核心是让适配第 1 种武器的强化材料数量严格大于其他任意武器。初始时每种武器都有一定数量的强化材料适配其中第 1 种武器有 cnt[1] 个。为了让第 1 种武器胜出我们需要把其他武器的强化材料改配到第 1 种武器上同时也要考虑把原本适配第 1 种武器的材料改走的情况但通常不会这样做因为这会增加第 1 种武器的数量成本。一个直观的贪心策略是枚举最终第 1 种武器拥有的强化材料数量 x要求 x 严格大于其他所有武器的数量。对于每个武器 ii 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; vectorint p(m), c(m); vectorvectorint 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; vectorint 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≤10001≤pi≤n1≤ci≤109。子任务编号得分占比nm120%≤2≤1000220%≤1000≤2360%≤1000≤1000样例解释花费 1将第三种强化材料的适配武器由 3 改为 1。此时武器 1 有 2 种强化材料适配武器 2 和武器 3 都各有 1 种强化材料适配满足适配第 1 种武器的强化材料种类数严格大于其他的武器。