Fork me on GitHub

[JZOJ]平均数

莫得传送门qwq,,,

题面

考虑二分平均值mid,设当前平均值小于等于mid的个数为$f(mid)$。当$f(mid)>k$,则缩小$mid$。然后剩下的问题就变成了怎么求出这个$f$了.
我们设𝑎数组前缀和为$sum_i$,那么区间$[𝑗+1,𝑖]$的平均值为$\frac{𝑠𝑢𝑚[𝑖]−𝑠𝑢𝑚[𝑗]}{𝑖−𝑗}$.
然后观察对于一对$(𝑖,𝑗)$:

显然,如果我们定义$v_i$表示$sum_i-mid \times i$的话,那么$f(mid)$即为$v$数组的逆序对.
所以我们要做的就是求出逆序对的个数即可,可以用树状数组或者归并排序轻松解决.

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[JZOJ]平均数

文章作者:KRrrrrrrrr

发布时间:2019年10月24日 - 14:10

最后更新:2019年11月05日 - 09:11

原始链接:http://krrrr.xyz/2019/10/24/JZOJ-平均数/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。