简答题
偏难
#18026
武器强化 时间限制:2.0 s 内存限制:512.0 MB 题面描述 小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第p i 种武器,小杨可以花…
武器强化
时间限制:2.0 s
内存限制:512.0 MB
题面描述
小杨有 n 种武器和 m 种强化材料。第 i 种强化材料会适配第pi种武器,小杨可以花费ci金币将该材料对应的适配武器修改为任意武器。
小杨最喜欢第 1 种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你帮小杨计算为了满足该条件最少需要花费多少金币。
输入格式
第一行包含两个正整数n,m,含义如题面所示。
之后 m 行,每行包含两个正整数pi,ci,代表第 i 种强化材料的适配武器和修改花费。
输出格式
输出一个整数,代表能够使适配第 1 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。
输入样例
输出样例
样例解释
花费 1,将第三种强化材料的适配武器由 3 改为 1。此时,武器 1 有 2 种强化材料适配,武器 2 和武器 3 都各有 1 种强化材料适配。满足适配第 1 种武器的强化材料种类数严格大于其他的武器。

对于全部数据,保证有1≤n,m≤1000,1≤pi≤n,1≤ci≤109。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">def calc(aim, n, cnt, cs):
cur_cnt = cnt[0]
res = 0
tmp = []
for i in range(1, n):
buy = max(len(cs[i]) - aim + 1, 0)
for j in range(buy):
res += cs[i][j]
cur_cnt += buy
for j in range(buy, len(cs[i])):
tmp.append(cs[i][j])
tmp.sort()
for i in range(aim - cur_cnt):
res += tmp[i]
return res
n, m = map(int, input().split())
cnt = [0] * n
cs = [[] for _ in range(n)]
for _ in range(m):
p, c = map(int, input().split())
cnt[p - 1] += 1
cs[p - 1].append(c)
for i in range(n):
cs[i].sort()
ans = 1000000000000000000
for i in range(max(cnt[0], 1), m + 1):
ans = min(ans, calc(i, n, cnt, cs))
print(ans)</pre>
这道题暂未补解析。