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 }

View Code

　　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 }

View Code