NOIP2021 T3乱搞

monstersqwq · 2021-11-20 17:25:14 · 题解

upd:官方数据极端憨批 x=14 过了。

首先发现给出的条件实质上是差分数组交换两个数，于是换成差分数组上的前缀和的方差。

经过一些拆式子之后得到了答案为 \sum\limits_{i=1}^{n-1}a_i(n-i)((\sum\limits_{i=1}^j2ja_j)-ia_i)，我们的目标是让这个东西最小。

写出一个爆搜之后你会发现有最优解的排布一定是先降再升高，于是就会有一个 O(n2^n) 的约 48pts 的做法。

以 a_i 为主元，发现是个二次多项式，二次项系数是 (n-i)i，一次项系数是 2((n-i)\sum\limits_{j=1}^{i-1}ja_j+i\sum\limits_{i=j+1}^{n-1}(n-j)a_j)。

然后如果你依照刚才 48 的思路，从两边往中间填数，实际上每个数的贡献就是二次项系数统计上在加上一次项系数中已经填的数的贡献，然后你枚举它往左边加数还是右边加数，就得到了一个 O(n) 的牛逼做法！

显然是错的，样例二都跑不明白。

使用大眼观察法，发现错在了差分数组左右两侧的大数上。

然后，进行一个结合，先爆搜一下两边数，有那么一二十个吧，然后再贪心填中间的，如果设你搜的个数为 x 复杂度大约是 O(2^xn)，考场上我取 x=19，18 会在最后一个大样例上错掉，20 常数翻倍可能要跑到两三秒，而 19 差不多考场垃圾机子没吸氧只跑了一点五秒。

乱搞，确定性算法，不同于随机化，你值得拥有