首页 > 其他 > 详细

Educational Codeforces Round 108 (Rated for Div. 2) C

时间:2021-04-30 20:47:14      阅读:30      评论:0      收藏:0      [点我收藏+]
#include <bits/stdc++.h>
#define priority_queue < ll, std::vector<ll>, std::greater<ll> > mnheap;
#define REP(i,a,b) for (auto i = a; i != b; i++)
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define eb emplace_back
#define f first
#define s second
#define pb push_back
using namespace std;
void read(int n,vector<int>& x)
{
    x.clear();
    x.resize(n);
    for(int i = 0;i<n;i++)
    {
        cin>>x[i];
    }

}
void read(int n,int m,vector<vector<int>>& x)
{
    x.clear();
    x.resize(n,vector<int>(m));
    for(int i = 0;i<n;i++)
    {
        for(int j = 0 ;j<m;j++)
            cin>>x[i][j];
    }
}
void read(int n,vector<vector<int>>& x)
{
    x.clear();
    x.resize(n+1);
    for(int i = 0;i<n-1;i++)
    {
         int a,b;
         cin>>a>>b;
         x[a].pb(b);
         x[b].pb(a);
    }
}
void read(int n,vector<vector<int>>& x,int m)
{
    x.clear();
    x.resize(n+1);
    for(int i = 0;i<m;i++)
    {
         int a,b;
         cin>>a>>b;
         x[a].pb(b);
         x[b].pb(a);
    }
}
void read(int n,vector<ll>& x)
{
    x.clear();
    x.resize(n);
    for(int i = 0;i<n;i++)
    {
        cin>>x[i];
    }
}
bool comp(vector<ll>& a,vector<ll>& b){
    return a.size() > b.size();
}
int main()
{
    std::ios::sync_with_stdio(false);
    int T = 1;
    cin>>T;
    for(int t = 1;t<=T;t++)
    {
        // cout<<"Case #"<<t<<": ";
        int n;
        cin>>n;
        vector<ll> u;
        read(n,u);
        vector<vector<ll>> skills(n);
        vector<ll> sizes(n);
        vector<vector<ll>> pref(n);
        for(int i = 0;i<n;i++){
            ll x;
            cin>>x;
            skills[u[i]-1].pb(x);
            sizes[u[i]-1]++;
        }
        sort(all(skills),comp);
        sort(rall(sizes));
        for(int i =0;i<n;i++){
            sort(rall(skills[i]));
        }
        for(int i = 0;i<n;i++){
            for(int j=0;j<skills[i].size();j++){
                if(j == 0){
                    pref[i].pb(skills[i][j]);
                }
                else{
                    pref[i].pb(pref[i].back() + skills[i][j]);
                }
            }
        }
        for(int i = 1;i<=n;i++){
            ll sum = 0;
            for(int j = 0;j<n;j++){
                if(sizes[j] < i){
                    break;
                }
                else{
                    ll x = sizes[j] / i;
                    sum += pref[j][x*i-1];
                }
            }
            cout<<sum<<" ";
        }

        cout<<endl;

    }

    return 0;
}

 

Educational Codeforces Round 108 (Rated for Div. 2) C

原文:https://www.cnblogs.com/qq1415584788/p/14723237.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!