https://codeforc.es/contest/1082/problem/C
题目大意:有m个类型,n个人,每个人有一个所属类型k和一个能力v,要求所选的类型的人个数相等并且使v总和最大(n,m<=1e5)
题解:用vector存下每种类型的各个v并且每种类型根据v按从大到小排序,然后处理出每种类型的前缀和,然后扫每种类型的所有前缀和,如果该类型在i处的前缀和大于0,则相应的ans[i]加上这个类型在i处的前缀和,最后求出max(ans[i])(1<=i<=n)即可.
注意:这题的外层循环应该是遍历m个类型,然后扫每种类型的前缀和来更新ans[i],这样子因为一共n个人,所以最多n次扫描过程复杂度为O(n),这种方式由于是根据每个类型的size来遍历的会减少很多无用的遍历,而如果外层循环是长度n,然后根据长度来更新ans[i],这样子会无视类型长度,进行很多次无用的遍历,复杂度是O(m*n),显然会T掉
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9+;
vector<int>vc[];
vector<ll>sum[];
ll ans[];
int main()
{
// freopen("in.txt","r",stdin);
int n,m;
cin>>n>>m;
int aa,bb;
int maxx=;
for(int i=;i<n;i++){
scanf("%d%d",&aa,&bb);
vc[aa].push_back(bb);
maxx=max(maxx,aa);
}
int minn=;//
for(int i=;i<=maxx;i++){
minn=max(minn,(int)vc[i].size());
sort( vc[i].begin(),vc[i].end(),greater<int>() );
for(int j=;j<vc[i].size();j++){ if(j)sum[i].push_back(sum[i][j-]+vc[i][j]);
else {sum[i].push_back(vc[i][j]);}
}
}
/*for(int i=1;i<=minn;i++){
for(int j=1;j<=maxx;j++){
if(vc[j].size()>=i&&sum[j][i-1]>=0){
ans[i]+=sum[j][i-1];
}
}
}*///错误的扫描方式,会T
for(int i=;i<=maxx;i++){
for(int j=;j<vc[i].size();j++){
if(sum[i][j]>=){
ans[j+]+=sum[i][j];
}
}
}//正确的扫描方式
ll aans=;
for(int i=;i<=minn;i++){
aans=max(ans[i],aans);
}
cout << aans<<endl;
return ;
}