A29867. 武器强化
填空题
困难
知识点
题目描述
武器强化
时间限制：2.0 s 内存限制：512.0 MB
题目描述
小杨有n种武器和m种强化材料。第 i 种强化材料会适配第pi种武器，小杨可以花费ci金币将该材料对应的适配武器修改为任意武器。
小杨最喜欢第1种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。
输入格式
第一行包含两个正整数n,m，含义如题目所示。
之后m行，每行包含两个正整数pi,ci ，代表第 i 种强化材料的适配武器和修改花费。
输出格式
输出一个整数，代表能够使适配第1种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。
输入样例
4 4
1 1
2 1
3 1
3 2
输出样例
1
样例解释
花费1，将第三种强化材料的适配武器由3改为1。此时，武器1有2种强化材料适配，武器2和武器3都各有1种强化材料适配。满足适配第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";
}
上一题
下一题