洛谷B4071 GESP五级 武器强化

 题面：

题目大意：

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

思路：

        枚举第一种武器的最终材料数，假设为i，那么其他各种武器最多为i−1，对于多于i−1的肯定要锻造掉，那么锻造掉哪些呢，对于同一个武器，一定优先锻造花费金币少的材料。所有武器的材料锻造完之后，如果第一种还是不够i怎么办？ 显然剩下的各种武器材料数都小于i了，那么没了限制，我们优先选花费金币最少的，因此把剩下的所有材料的花费里进行排序，从小到大取。 此题枚举+贪心

解法:

假设结果为ans。可以用数组csp表示适配第p种武器的所有材料花费,然后用cnt表示共有cnt;适配第p种武器的材料,你也可以理解为csp的长度。 随后,开贪,既然要求最少花费,那么就将csp小的排在前,极易证明,如果不把c8p小的排在前,
求花费时加不到cspmin(csp中最小值),花费就不是最小的。排序后,核心来了。定义i为遍历m种强化材料的循环变量。因为题面有:
        小杨最喜欢第1种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你
        帮小杨计算为了满足该条件最少需要花费多少金币。
所以我们尽量使用cnt中材料多中最便宜的材料,使用这种材料将第i种武器改成第1种武器,随后ans判断当前花费和ans取最小值,即ans<-min(ans,当前花费)。
如何算当前花费呢?先令curcnt<-cnt1,res<-0(res表示当前花费)并定义数组tmp表示最便宜的材料有那些。因为要让第1种武器适配该武器的强化材料种类数尽可能多,必然会产生一个单调上升序列:{1,2,3,4,}。假设ii指序列中的数(对应代码中f函数的形参),如果cnti一ii十1是负数,说明csi中的长度比ii短,如果比ii长,res加上花费即可。
假设b是csi中减去ii加一的长度,然后将csi的数值加入到tmp中。curcnt指的是tmp的长度,所以每轮循环curcnt一curcnt十b。但是如果cnti一ii十1是负数,curcnt就小了,所以b÷min(cnti-ii+1,0)。
最后对tmp进行排序,res加上tmp前ii一curcnt个数,然后ans和res进行比较ans取小的。最后开longlong就行了。

代码：

#include<bits/stdc++.h>
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;
}

完结撒花！！