题面
有 n 个学生和 n 所大学，每个学生在其中一所大学中学习，且各有一个能力值
s
i
s_i
si 。
某次组队打比赛的召集令会给一个数字 k ，表示团队数量。然后每所大学会先把自己的所有学生按照
a
i
a_i
ai 从大到小排序，选前
k
k
k 个组个队，前
k
+
1
k+1
k+1 到
2
k
2k
2k 个组个队，……剩下最后不足
k
k
k 个学生，这些学生就不能组队。
每次召集的总能力值为所有组出来的队伍的每个学生的能力值之和。现在有
n
n
n 次召集令，给出的
k
k
k 分别是 1~n，分别求每次召集的总能力值。
题解
我这个做法被 nlogn 做法吊打，本愧于过此题，然所用方法有点思维，不如写来搏之一笑。
分别求每个学生的贡献。
假设当前学生在他(她)的大学里排名为倒数第
y
y
y ，而大学里总共
x
x
x 个学生，那么该学生对数字为
k
k
k 的召集令有贡献当且仅当
x
m
o
d
k
<
y
x\!\!\!\!\mod k<y
xmodk<y
变一下式子：
x
−
⌊
x
k
⌋
∗
k
<
y
⇔
x
−
y
<
⌊
x
k
⌋
∗
k
⇔
⌊
x
−
y
k
⌋
<
⌊
x
k
⌋
x-\left\lfloor \frac{x}{k}\right\rfloor*k<y\\ ~~\Leftrightarrow~~ x-y<\left\lfloor \frac{x}{k}\right\rfloor*k\\ ~~\Leftrightarrow~~ \left\lfloor \frac{x-y}{k}\right\rfloor<\left\lfloor \frac{x}{k}\right\rfloor
x−⌊kx⌋∗k<y ⇔ x−y<⌊kx⌋∗k ⇔ ⌊kx−y⌋<⌊kx⌋
如果我们已知
⌊
x
k
⌋
=
d
\left\lfloor \frac{x}{k}\right\rfloor=d
⌊kx⌋=d，那么
⌊
x
−
y
k
⌋
<
d
⇔
x
−
y
<
d
k
⇔
⌊
x
−
y
d
⌋
<
k
\left\lfloor \frac{x-y}{k}\right\rfloor<d\\ ~~\Leftrightarrow~~ x-y<dk\\ ~~\Leftrightarrow~~ \left\lfloor \frac{x-y}{d}\right\rfloor<k
⌊kx−y⌋<d ⇔ x−y<dk ⇔ ⌊dx−y⌋<k
好，这是个关于
k
k
k 的范围的表达式了，由于我们知道
⌊
x
k
⌋
\left\lfloor \frac{x}{k}\right\rfloor
⌊kx⌋ 随着
k
k
k 的不同只有大约
x
\sqrt x
x
[
l
,
r
]
[l,r]
[l,r] 和
d
d
d，就对答案序列的
[
max
(
⌊
x
−
y
d
⌋
+
1
,
l
)
,
r
]
[\max(\left\lfloor \frac{x-y}{d}\right\rfloor+1,l),r]
[max(⌊dx−y⌋+1,l),r] 产生贡献。
对每个学生都计算一次，复杂度
O
(
n
n
)
O(n\sqrt n)
O(nn
)。
CODE
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
LL read() {
LL f = 1,x = 0;char s = getchar();
while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
return f * x;
}
int n,m,i,j,s,o,k;
int a[MAXN];
vector<int> u[MAXN];
LL sm[MAXN];
bool cmp(int x,int y) {return a[x] > a[y];}
int main() {
int T = read();
while(T --) {
n = read();
for(int i = 1;i <= n;i ++) u[i].clear(),sm[i] = 0;
for(int i = 1;i <= n;i ++) {
s = read(); u[s].push_back(i);
}
for(int i = 1;i <= n;i ++) {
a[i] = read();
}
for(int i = 1;i <= n;i ++) {
sort(u[i].begin(),u[i].end(),cmp);
int X = u[i].size();
for(int j = 0,nm = X;j < (int)u[i].size();j ++,nm --) {
int con = a[u[i][j]];
sm[1] += con; sm[nm+1] -= con;
for(int l = nm+1,r = 1;l <= X;l = r+1) {
r = X/(X/l); int d = X / l;
int ll = max(l,((X-nm)/d) + 1);
if(ll <= r) {
sm[ll] += con; sm[r+1] -= con;
}
}
}
}
for(int i = 1;i <= n;i ++) {
sm[i] += sm[i-1];
printf("%lld ",sm[i]);
}ENDL;
}
return 0;
}
