CF educational 108 C Berland Regional

题目要求:
题目大意：每个学校有很多人，每个人有一个能力值。现在要组队参赛，假如现在一支队伍k人，最终参赛总人数是k的倍数，而且只能同校组队。问队伍人数从1~n，这n种情况每种情况整个比赛所有参赛队员的最大能力和。
思路:就是模拟,但要注意方***不会超时.
我最初得思路是k从到n,每次遍历这个学校对答案的贡献,不出所料超时;后面更改用前缀和来保存每个学校的贡献.但依旧超时.时间O(n^2).

for(int i=1;i<=n;i++)//k的值
        {
            ans=0;
            for(int j=1;j<=n;j++)//第几个学校
            {
                if(s[j].size()<i) continue;
                else
                {
                    int k = i , siz = s[j] . size();
                        ans += dis[j][ siz - siz%k -1 ];
                }
            }
            printf("%lld ",ans);
            if(i==n) printf("\n");
        }

后面我们可以想到,每个学校人数都不一样,当只有一个学校的人数大于等于k值时,我们依旧要遍历其他学校的学生,这样会浪费很多时间,但是如果我们计算每个学校对答案的贡献时,就不用浪费时间去遍历不满足要求的学校的学生了.详情看代码.

 for(int i=1;i<=n;i++){
            if(s[i].size()==0) continue;
                int siz=s[i].size();
            for(int j=1;j<=siz;j++)//k的值
            {
                an[j]+=dis[i][siz-siz%j-1];
            }
        }

下面是AC代码.

#include <bits/stdc++.h>
//#define ll long long;
using namespace std;
const int N=2e5+5;
multiset< long long , greater<long long> > s[N];//降序排列
vector<long long> dis[N];
int a[N];
long long an[N];
void init()
{
    for(int i=1;i<=N;i++)
    {
        if(s[i].size()!=0) s[i].clear();
        if(dis[i].size()!=0) dis[i].clear();
    }
    memset(a,0,sizeof(a));
    memset(an,0,sizeof(an));
}
int main()
{
    int t;
    scanf("%d",&t);
    int n;
    int x,y;
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            a[i]=x;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&y);
            s[ a[i] ].insert(y);
        }
        long long ans;
        for(int i=1;i<=n;i++)
        {
            ans=0;
            if(s[i].size()==0) continue;
            multiset<long long>::iterator k = s[i] . begin();
            while( k != s[i].end() )
            {
                ans += *k;
                dis[i].push_back(ans);k++;
            }
        }
        for(int i=1;i<=n;i++){
            if(s[i].size()==0) continue;
                int siz=s[i].size();
            for(int j=1;j<=siz;j++)//k的值
            {
                an[j]+=dis[i][siz-siz%j-1];
            }
        }
        for(int i=1;i<=n;i++) printf("%lld ",an[i]);
        printf("\n");
        init();
    }
    return 0;
}