简答题
偏难
#20700
武器强化 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第 p i 种武器,小杨可以…
武器强化
时间限制:1.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 种武器的强化材料种类数严格大于其他的武器。

对于全部数据,保证有 1≤n,m≤1000,1≤pi≤n,1≤ci≤109。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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";
}</pre>
这道题暂未补解析。