UOJ Logo

NOI.AC

2S 512MB

#131. B君的第二题

Statistics

【题目描述】

战场上打不赢,谈判桌上怎么谈,结果都是⼀样的。

现在议会正在进一场选举。这场选举一共有 $n$ 个党派,需要选出 $m$ 个席位。选民们并不能投票给个人,只能投票给自己支持的党。每个党需要推出自己的 $m$ 个候选人。

假设第 $i$ 个党获得了 $p_i$ 票,那么第 i 个党的第 $j(1 ≤ j ≤ m)$ 个候选人的权值是 $p_i/j$。将所有 $nm$ 个候选人按权值从大到小排序,如果权值相同, 谁的党编号更小,谁在前面。权值最大的 m 个候选人胜出。

现在已知每个党的得票情况,你来帮忙算一下每个党可以获得多少席位。

【输入格式】

第一行两个整数 n, m。

接下来 n 行,每行一个整数 $p_i$,表示第 $i$ 个党获得的票数。

【输出格式】

输出共 n 行,第 i 行表示第 $i$ 个党获得的席位数。

【样例输入】

4 8
100
80
30
20

【样例输出】

4
3
1
0

【样例解释】

第一个党,前五名权值近似是 100, 50, 33, 25, 20。

第二个党,前五名权值近似是 80, 40, 27, 20, 16。

第三个党,前五名权值近似是 30, 15, 10, 8, 6。

第四个党,前五名权值近似是 20, 10, 7, 5, 4。

选取所有数字中最大的 m 个,四个党分别获得 4, 3, 1, 0 个席位。

计算权值的除法不做任何近似。样例为了便于理解,近似成了整数。

【样例输入】

2 1000000000
1
10000

【样例输出】

99990
999900010

【样例输入】

4 3
1
1
1
2

【样例输出】

1
1
0
1

【样例解释】

权值相同,编号较小的党排在前面。

【数据规模与约定】

对于 100% 的数据,满足 $1 ≤ n ≤ 105, 1 ≤ m ≤ 10^9, 1 \le p_i \le 10^9$。

对于 30% 的数据,满足 $1 ≤ n ≤ 10^3, 1 ≤ m ≤ 10^3$。

对于 70% 的数据,满足 $1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5$。