CF1854A2

引领天下 · 2023-07-30 01:49:01 · 题解

有趣的构造题。

提示：本题的简单版本对困难版本有一定启发作用，推荐搭配 A1 的题解 食用。

题意：

给定一个长度为 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 的时候是这么写的：

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 了一次。

此处提醒大家以我为戒，注意符号，切勿再犯。