思路

原题是这个:【Codeforces 626E】 Simple Skewness

题意:从数列里选出若干个数,使得他们的平均数减中位数最大。

这个问题有三个性质:

  • 答案一定是非零数。因为你只选择一个数的时候,答案为0;
  • 选出的数一定为奇数个。我们可以通过这个方法来证明:

假设原来我们选了 $2k$ 个数,这些数升序排列是 $a_1$ ~ $a_{2k}$ ,我们现在去掉 $a_{k+1}$ 这个数,答案一定不会变劣。

设原来的平均数为 $ av $,平均数的增量为:$$ΔAverage=\frac{av*2k-a_{k+1}}{2k-1}-av $$

中位数的增量为:$$ΔMedian=a_k-\frac{a_k+a_{k+1}}{2}$$

整理得:$$ΔAverage – ΔMedian = \frac{2av+(2k-1)(a_{k+1}-a_k)-a_{k+1}}{2(2k-1)}$$

上式显然大于零,证毕。

  • 选定中位数后,向选定数列中添加新数字,一定是选择了两边可选的最大数。不断添加新数字,平均数的变化是先增后减的,所以我们可以通过二分找到它的峰值。

结合以上三点,算法就非常地显然了:枚举每一个中位数,然后二分找到对应的平均数的最大值,更新答案。

代码

用VS写的,提交的时候要记得注释掉第一个库。

  1. Oh_GaGaGaGa
    Nov 06, 2018

    为什么二分的时候 没有改变mid呀。。这里好像仅仅变了l, r 而mid没变耶qwq
    ps. luogu上那篇题解好像也有这个毛病

    Reply
    • Oh_GaGaGaGa
      Nov 06, 2018

      对不起 没有看见define 请无视刚刚的评论谢谢

      Reply
      • xgzepto
        Nov 06, 2018

        没事,感谢您对待我题解的认真

        Reply
  2. CrazyDave
    Jun 09, 2018

    %%% XG

    Reply