乘法排序 题解

思路

最终数组严格递增，因此所有负数一定构成一个前缀，所有正数构成一个后缀。枚举负数前缀的长度 $k$。

在负数前缀内，若相邻原数满足 $a_i>a_{i+1}$，给它们乘同一个负数后顺序已经正确；否则必须在这两个位置之间产生一次额外的区间操作边界。在正数后缀内则相反：$a_i<a_{i+1}$ 时无需额外操作，$a_i\ge a_{i+1}$ 时必须增加一次边界。只要 $k>0$，还需要一次操作把整个前缀变为负数。任意大的整数乘数可以从边界向外依次选择，因此这些必要条件也足够。

所以固定 $k$ 的代价为

$$[k>0]+\#\{i<k:a_i\le a_{i+1}\}+\#\{i\ge k:a_i\ge a_{i+1}\},$$

其中相邻下标按分界两侧理解，不统计跨越正负分界的相邻对。

做法

子任务 1 枚举分界，再枚举所有相邻位置是否由不同操作块覆盖，检查所有必要边界并取最少操作数。

子任务 2 枚举分界 $k$，每次从头扫描负前缀与正后缀，直接计算上式。

完整做法先预处理每个后缀中的非递增相邻对数量。分界从左向右移动时，再维护负前缀中的非递减相邻对数量，每个分界即可 $O(1)$ 求值。

复杂度

子任务 1 的时间复杂度为 $O(n^2 2^n)$，空间复杂度为 $O(1)$。

子任务 2 的时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。

完整做法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$；所有复杂度均对单组数据而言。