简答题 偏难
#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&lt;bits/stdc++.h&gt; using namespace std; #define ll long long int n, m; int cnt[1010]; vector&lt;int&gt; cs[1010]; ll calc(int aim) { int cur_cnt = cnt[1]; ll res = 0; vector&lt;int&gt; tmp; for (int i = 2; i&lt;=n; i++) { int buy = max((int)cs[i].size() - aim + 1, 0); for (int j = 0; j &lt; buy; ++j) { res += (ll)cs[i][j]; } cur_cnt += buy; for (int j = buy; j &lt; cs[i].size(); ++j) { tmp.push_back(cs[i][j]); } } sort(tmp.begin(), tmp.end()); for (int i = 0; i &lt; aim - cur_cnt; i++) { res += (ll)tmp[i]; } return res; } signed main() { // freopen("06.in", "r", stdin); cin &gt;&gt; n &gt;&gt; m; for (int i = 1; i &lt;=m; i++) { int p, c; cin &gt;&gt; p &gt;&gt; c; cnt[p]++; cs[p].push_back(c); } for (int i = 1; i &lt;=n; i++) { sort(cs[i].begin(), cs[i].end()); } ll ans = 1e18; for (int i = max(cnt[1], 1); i &lt;= m; ++i) { ans = min(ans, calc(i)); } cout &lt;&lt; ans &lt;&lt; "\n"; }</pre>
这道题暂未补解析。