Problem
Key Idea
- ๊ฐ university ๋ณ๋ก ๋ฐ๋ก ๊ณ์ฐ์ด ๊ฐ๋ฅํ๋ค.
- ํ university์ ํ์ ์๊ฐ \(sz\) ๋ผ๋ฉด, \(1 \le k \le sz\) ์ธ k๊ฐ์๋ง ์ํฅ์ด ์๋ค.
์ฒซ ๋ฒ์งธ ์์.
7
1 2 1 2 1 2 1
6 8 3 1 5 1 5
๊ฐ university ๋ณ๋ก list์ ๋ด๊ณ , sortingํ๋ฉด
univ[1]: 3 5 5 6
univ[2]: 1 1 8
\(univ[1]\) ๊ณ์ฐ: \(k = 3\) ์ผ๋ 6์ด ์ ์ธ๋๋ฉด์, \(ans[3]\)์๋ง 6์ด ๋น ์ง๋ค.
ans: 0 19 19 13 19 0 0 0
์ฆ, \(sz \mod k\) ๊ฐ ๋งํผ ์์์๋ถํฐ(์์๊ฒ๋ถํฐ) ๋น ์ง๋ค.
- university๋ณ๋ก sort.
- \(univ[i] (1 \le i \le n)\) ๋ฐฐ์ด์ ๋์ ํฉ ๋ฐฐ์ด๋ก ๋ณํ
- \(univ\) ๋ฐฐ์ด์ ์ํํ๋ฉด์, ๊ฐ \(k\)๊ฐ \((1 \le k \le sz)\)์ ๋ํด \((์ดํฉ - univ[i][sz\%k-1])\) ์ \(ans[k]\)์ ๋ํด์ค๋ค.
- Time: \(O(n{\log}n)\)
Implementation
/**
* author: jooncco
* written: 2021. 5. 8. Sat. 00:22:56 [UTC+9]
**/
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
typedef vector<ll> vl;
int t,n;
ll u[200010], s;
int main() {
FAST_IO;
cin >> t;
while (t--) {
cin >> n;
for (int i=0; i < n; ++i) cin >> u[i];
vector<vl> univ(n+1,vl());
ll ans[200010]= {0};
for (int i=0; i < n; ++i) {
cin >> s;
univ[u[i]].push_back(s);
}
for (int i=1; i <= n; ++i) {
int sz= univ[i].size();
if (sz) {
sort(univ[i].begin(),univ[i].end());
for (int j=1; j < sz; ++j) univ[i][j] += univ[i][j-1];
for (int k=1; k <= sz; ++k) {
ans[k] += univ[i][sz-1];
if (sz%k > 0) ans[k] -= univ[i][sz%k-1];
}
}
}
for (int i=1; i <= n; ++i) {
if (i > 1) cout << " ";
cout << ans[i];
}
cout << "\n";
}
}
Leave a comment