C. Multi-Subject Competition 思维+前缀和+填表加减复杂度（复杂度计算错误）
题意: 给出n个学生 m类题目 每个人会做s[i]类的题 并且做这个题的能力为r[i] 组成一个竞赛队 要求可以选择一些题目 在竞赛队中 擅长每一个题目的
人数要均等 求max(sigma(r[i]))
思路：贪心思想 每类题目选k个学生 先对每一类学生的能力值排序 如果这k个学生的能力值大于0 就选上 一开始写的是类似扫描的思想 从k从1---max（擅长一类题目的学生） 然后把他们前k个相加
如果擅长其中一类题目的sum<=0或者没有k个学生擅长该类题目就忽略 这样在枚举的时候就会爆炸T O（n*m） 换一个想法 用填表的思想ans[i]表示选取i个学生时候的max(sigma(r[i])) 每次枚举一类 如果
前缀和sum大于0就把它填在适当的ans[i]中 这样复杂度就为O（nlogn+m）
此题注意扫描不行就换填表 以减少复杂度
AC：
1 #include<bits/stdc++.h> 2 #define pb push_back 3 using namespace std; 4 const int maxn=2e5+6; 5 const int inf =0x3f3f3f3f; 6 vector<int>v[maxn]; 7 vector<int>sum[maxn]; 8 bool cmp(int x,int y){ 9 return x>y; 10 } 11 int vis[maxn]; 12 int ans[maxn]; 13 int main(){ 14 int n,m; 15 scanf("%d%d",&n,&m); 16 for(int i=1;i<=n;i++){ 17 int a,b; 18 scanf("%d%d",&a,&b); 19 v[a].pb(b); 20 } 21 for(int i=1;i<=m;i++){ 22 sort(v[i].begin(),v[i].end(),cmp); 23 } 24 int ans1=0; 25 int maxsize=0; 26 for(int i=1;i<=m;i++){ 27 int sum=0; 28 for(int j=0;j<v[i].size();j++){ 29 sum+=v[i][j]; 30 if(sum>0)ans[j]+=sum; 31 else break; 32 } 33 maxsize=max(maxsize,int(v[i].size())); 34 } 35 for(int i=0;i<maxsize;i++)ans1=max(ans1,ans[i]); 36 cout<<ans1<<endl; 37 38 39 40 }
T：
1 #include<bits/stdc++.h> 2 #define pb push_back 3 using namespace std; 4 const int maxn=2e5+6; 5 const int inf =0x3f3f3f3f; 6 vector<int>v[maxn]; 7 vector<int>sum[maxn]; 8 bool cmp(int x,int y){ 9 return x>y; 10 } 11 int vis[maxn]; 12 int ans[maxn]; 13 int main(){ 14 int n,m; 15 scanf("%d%d",&n,&m); 16 for(int i=1;i<=n;i++){ 17 int a,b; 18 scanf("%d%d",&a,&b); 19 v[a].pb(b); 20 } 21 for(int i=1;i<=m;i++){ 22 sort(v[i].begin(),v[i].end(),cmp); 23 } 24 int big=inf; 25 int maxsize=0; 26 for(int i=1;i<=m;i++){ 27 int j; 28 for( j=0;j<int(v[i].size());j++){ 29 if(j>0) 30 sum[i].pb(sum[i][j-1]+v[i][j]); 31 else sum[i].pb(v[i][j]); 32 if(sum[i][j]<=0){ 33 break; 34 } 35 36 } 37 /* if(j>0&&sum[i][j-1]>0){ 38 sum[i].pb(-sum[i][j-1]); 39 }*/ 40 41 maxsize=max(maxsize,int(sum[i].size())); 42 } 43 44 int tmp=0; 45 int ans=0; 46 for(int i=0;i<maxsize;i++){ 47 tmp=0; 48 for(int j=1;j<=m;j++){ 49 if(vis[j]||i>=int(sum[j].size()))continue; 50 if(sum[j][i]<=0){ 51 vis[j]=1; 52 continue; 53 } 54 tmp+=sum[j][i]; 55 } 56 ans=max(tmp,ans); 57 } 58 59 /*for(int i=1;i<=m;i++){ 60 int sum=0; 61 for(int j=0;j<v[i].size();j++){ 62 sum+=v[i][j]; 63 if(sum>=0)ans[j]+=sum; 64 else break; 65 } 66 maxsize=max(maxsize,int(v[i].size())); 67 } 68 int ans1=0; 69 for(int i=0;i<maxsize;i++)ans1=max(ans1,ans[i]);*/ 70 71 cout<<ans<<endl; 72 73 74 75 }
查看15道真题和解析
