《B4071 [GESP202412 五级] 武器强化》

题目背景对应的选择、判断题试题 - GESP 202412 C 五级 - 洛谷有题题目描述小杨有 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将第三种强化材料的适配武器由 3 改为 1。此时武器 1 有 2 种强化材料适配武器 2 和武器 3 都各有 1 种强化材料适配满足适配第 1 种武器的强化材料种类数严格大于其他的武器。数据范围对于 100% 的数据保证 1≤n,m≤10001≤pi​≤n1≤ci​≤109。子任务编号得分占比nm120%≤2≤1000220%≤1000≤2360%≤1000≤1000代码实现#include bits/stdc.h using namespace std; typedef long long ll; vectorll costs[1005]; int n, m; int main() { cin n m; for (int i 1; i m; i) { int p; ll c; cin p c; costs[p].push_back(c); } for (int i 1; i n; i) { sort(costs[i].begin(), costs[i].end()); } ll ans LLONG_MAX; int init_cnt costs[1].size(); for (int k init_cnt; k m; k) { ll total_cost 0; int cur_cnt_1 init_cnt; vectorll all_other_costs; for (int i 2; i n; i) { int need max(0, (int)costs[i].size() - (k - 1)); for (int j 0; j need j costs[i].size(); j) { total_cost costs[i][j]; cur_cnt_1; } for (int j need; j costs[i].size(); j) { all_other_costs.push_back(costs[i][j]); } } if (cur_cnt_1 k) { sort(all_other_costs.begin(), all_other_costs.end()); for (int i 0; i k - cur_cnt_1 i all_other_costs.size(); i) { total_cost all_other_costs[i]; } } ans min(ans, total_cost); } cout ans endl; return 0; }