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掉
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<stack> 6 #include<vector> 7 #include<algorithm> 8 using namespace std; 9 typedef long long ll; 10 const int mod = 1e9+7; 11 vector<int>vc[100005]; 12 vector<ll>sum[100005]; 13 ll ans[100005]; 14 int main() 15 { 16 // freopen("in.txt","r",stdin); 17 int n,m; 18 cin>>n>>m; 19 int aa,bb; 20 int maxx=1; 21 for(int i=0;i<n;i++){ 22 scanf("%d%d",&aa,&bb); 23 vc[aa].push_back(bb); 24 maxx=max(maxx,aa); 25 } 26 int minn=0;// 27 for(int i=1;i<=maxx;i++){ 28 minn=max(minn,(int)vc[i].size()); 29 sort( vc[i].begin(),vc[i].end(),greater<int>() ); 30 for(int j=0;j<vc[i].size();j++){ 31 32 if(j)sum[i].push_back(sum[i][j-1]+vc[i][j]); 33 else {sum[i].push_back(vc[i][j]);} 34 } 35 } 36 /*for(int i=1;i<=minn;i++){ 37 for(int j=1;j<=maxx;j++){ 38 if(vc[j].size()>=i&&sum[j][i-1]>=0){ 39 ans[i]+=sum[j][i-1]; 40 } 41 } 42 }*///错误的扫描方式,会T 43 for(int i=1;i<=maxx;i++){ 44 for(int j=0;j<vc[i].size();j++){ 45 if(sum[i][j]>=0){ 46 ans[j+1]+=sum[i][j]; 47 } 48 } 49 }//正确的扫描方式 50 ll aans=0; 51 for(int i=1;i<=minn;i++){ 52 aans=max(ans[i],aans); 53 } 54 cout << aans<<endl; 55 return 0; 56 }