简答题 偏难
#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 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。

输入样例

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: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>
这道题暂未补解析。