Codeforces Round #728 (Div. 2) ABC 题解 (Java/C++)

A. Pretty Permutations

显然，只需要相邻两位相互交换位置即可。对于n等于奇数的情况，只需最后三位相互交换即可。

Java

C++

对原数组a排序。于是，对于任意一个j，我们可以按a值从小到大枚举。一旦发现其乘积大于2n就不再往后枚举。这样时间复杂度大约是$\frac{n}{a_1}+\frac{n}{a_2}+\frac{n}{a_3}+...\frac{n}{a_n}$。

Java

C++

显然，为了正值尽可能小，我们尽可能的复用之前的路径。于是正值的路大概如下图：

接着，我们为了负值尽可能大，于是我们顺着正值的路依次构建即可：

Java

C++