自动搬运

查看原文

来自洛谷，原作者为

	niuniudundun 天禄

搬运于2025-08-24 21:16:53，当前版本为作者最后更新于2024-12-13 18:34:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题

题目大意

有 $n$ 种武器和 $m$ 种强化材料。第 $i$ 种强化材料会适配第 $p_i$ 种武器，小杨可以花费 $c_i$ 金币将该材料对应的适配武器修改为任意武器。小杨最喜欢第 $1$ 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

解法

假设结果为 $ans$。

可以用数组 $cs_{p}$ 表示适配第 $p$ 种武器的所有材料花费，然后用 $cnt_i$ 表示共有 $cnt_i$ 适配第 $p$ 种武器的材料，你也可以理解为 $cs_p$ 的长度。

随后，开贪，既然要求最少花费，那么就将 $cs_p$ 小的排在前，极易证明，如果不把 $cs_p$ 小的排在前，求花费时加不到 $cs_{p,min}$（$cs_p$ 中最小值），花费就不是最小的。

排序后，核心来了。定义 $i$ 为遍历 $m$ 种强化材料的循环变量。因为题面有：

小杨最喜欢第 $1$ 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨

计算为了满足该条件最少需要花费多少金币。

所以我们尽量使用 $cnt$ 中材料多的，$cs_{1\cdots cnt_i}$ 中最便宜的材料，使用这种材料将第 $i$ 种武器改成第 $1$ 种武器，随后 $ans$ 判断当前花费和 $ans$ 取最小值，即 $ans\gets \min(ans,当前花费)$。

如何算当前花费呢？先令 $curcnt\gets cnt_1,res\gets 0$（$res$ 表示当前花费）并定义数组 $tmp$ 表示最便宜的材料有那些。因为要让第 $1$ 种武器适配该武器的强化材料种类数尽可能多，必然会产生一个单调上升序列：$\left \{ 1,2,3,4,\cdots \right \}$。假设 $ii$ 指序列中的数（对应代码中 $f$ 函数的形参），如果 $cnt_i-ii+1$ 是负数，说明 $cs_i$ 中的长度比 $ii$ 短，如果比 $ii$ 长，$res$ 加上花费即可。

假设 $b$ 是 $cs_i$ 中减去 $ii$ 加一的长度，然后将 $cs_i$ 的数值加入到 $tmp$ 中。$curcnt$ 指的是 $tmp$ 的长度，所以每轮循环 $curcnt\gets curcnt+b$。但是如果 $cnt_i-ii+1$ 是负数，$curcnt$ 就小了，所以 $b\gets \min(cnt_i-ii+1,0)$。

最后对 $tmp$ 进行排序，$res$ 加上 $tmp$ 前 $ii-curcnt$ 个数，然后 $ans$ 和 $res$ 进行比较 $ans$ 取小的。

最后开 long long 就行了。

代码

#include<iostream>
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int maxm=1001,maxn=maxm;
long long n,m,p[maxn],c[maxm];
long long cnt[maxn];
vector<int> cs[maxn];
long long ans=1e18;
long long f(int ii){
	long long curcnt=cnt[1],res=0;
	vector<int> tmp;
	for(int i=2;i<=n;i++){
		int b=max((int)(cs[i].size()-ii+1),0);
		for(int j=0;j<b;j++){
			res+=cs[i][j];
		}
		curcnt+=b;
		for(int j=b;j<cs[i].size();j++){
			tmp.push_back(cs[i][j]);
		}
	}
	sort(tmp.begin(),tmp.end());
	for(int i=0;i<ii-curcnt;i++){
		res+=tmp[i];
	}
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>p[i]>>c[i];
		cnt[p[i]]++;
		cs[p[i]].push_back(c[i]);
	}
	for(int i=1;i<=n;i++){
		sort(cs[i].begin(),cs[i].end());
	}
	for(int i=max((long long)(cnt[1]),1ll);i<=m;i++){//注意范围！
		ans=min(ans,f(i));
	}
	cout<<ans<<endl;
	return 0;
}