CF1854A2

有趣的构造题。 **提示：本题的简单版本对困难版本有一定启发作用，推荐搭配 [A1 的题解](https://www.luogu.com.cn/blog/yltx/cf1854a1-post) 食用。** 题意： 给定一个长度为 $n$ 的序列，现在可以进行以下操作： - 选择 $i,j$（注意 $i$ 可以等于 $j$），将 $a_i\leftarrow a_i+a_j$。 做法： 我们注意到在做 A1 的 $a_n<0$ 的情况时，我们使用了一个很香的后缀和做法。 这个做法能否扩展呢？ 显然是可以的。对于 $a_i$ 全负的情况，做后缀和即满足题意；对 $a_i$ 全正的情况，做前缀和即满足题意。 前缀和 和 后缀和 都需要 $n-1$ 次操作，于是问题就变成了如何在 $12$ 次内使 $a_i$ 全正或全负。 一个很自然的想法是用多的同化少的，即正的 $a_i$ 较多的时候就填平负的 $a_i$，否则填平正的。 以下以正的较多的情况展开讨论： 考虑这个做法什么时候会被卡到极限。 显然是正的 $a_i$ 的最大值（记为 $A$）远小于负的 $a_i$ 的最小值（记为 $B$），极限情况是 $A=1,B=-20$。 这种情况下我们想要让 $A>-B$ 需要 $5$ 次操作，这样一来留给我们填平负的 $a_i$ 的次数就只剩下了 $7$ 次。 那如果有 $8$ 个负数呢？ 既然正的填负的超了，我们就考虑反过来负的填正的，这样的操作次数最多正好是 $20-8=12$ 次。 最后总次数刚好卡进 $31$ 次。~~妙的一笔~~ 对于 $A$ 更大或者 $B$ 更小的情况，讨论后即可发现正填负和负填正总有一种是正确的，详细的讨论过程与以上类似，这里就不展开了。 而负的 $a_i$ 较多的情况与正的较多的情况极为相似，此处同样不再赘述。 我的代码存在大量重复片段，这里就不贴出来了。 --- 题外话：有小天才上来看到 A1，A2 没有思路，于是去开 B ，吃了 5 发罚时，最后 82min 才过 B，然后 17min 切 A1，28min 切 A2。~~我觉得我能吹一年~~ 值得一提的是，这个小天才在求 $B$ 的时候是这么写的： ```cpp if(a[i]>0){ cnt[0]++; if(a[i]>mx)mx=a[i],mxi=i; }else{ cnt[1]++; if(a[i]<mn)mn=a[i],mni=i; } ``` 然后最小值求了个 0 出来，在 #2 TLE 了一次。 此处提醒大家以我为戒，注意符号，切勿再犯。