CF2041M Selection Sort

 每个选修算法课程的学生本周都需要提交一次作业。任务是实现一个 $O(n^2)$ 时间复杂度的算法，将给定的 $n$ 个整数按非递减顺序排序。Alice 已经完成了她的作业，她的实现如下所示： ``` int alice_sort(int *s, int n){ for(int i = 0; i < n; ++i){ for(int j = i + 1; j < n; ++j){ if(s[i] > s[j]){ int swap = s[i]; s[i] = s[j]; s[j] = swap; } } } return 0; } ``` 虽然你可以访问到 Alice 的代码，但你并不想直接照搬。你希望将 Alice 的排序函数作为你自己解决方案的一个构建模块。你可以通过以下两种方式使用她的函数，但每种方式最多只能使用一次。这两种操作的调用顺序可以任意。 - 前缀排序：选择一个长度 $i \in \{1, 2, \ldots, n\}$，调用 $\texttt{alicesort(}s, i\texttt{)}$。这会将数组 $s$ 的前 $i$ 个元素排序。 - 后缀排序：选择一个长度 $i \in \{1, 2, \ldots, n\}$，调用 $\texttt{alicesort(}s+n-i, i\texttt{)}$。这会将数组 $s$ 的后 $i$ 个元素排序。 由于排序算法的时间复杂度，执行一次前缀或后缀排序的代价为 $i^2$，其中 $i$ 是所选子数组的长度。你的目标是，按照上述规则，使用 Alice 的函数对输入数组 $s$ 的 $n$ 个整数进行非递减排序，并求出最小的总代价。 例如，设 $s=[3,2,5,5,4,1]$。我们可以先对长度为 $4$ 的后缀排序，数组变为 $[3,2,1,4,5,5]$。然后对长度为 $3$ 的前缀排序，数组变为 $[1,2,3,4,5,5]$，此时数组已排序。总代价为 $4^2+3^2=25$。再如，设 $s=[4,3,2,1]$，只需对长度为 $4$ 的前缀排序即可完成排序，总代价为 $4^2=16$。

第一行包含一个整数 $n$，表示数组 $s$ 的元素个数。第二行包含 $n$ 个整数，表示 $s=[s_0, s_1, \ldots, s_{n-1}]$。 - $1 \le n \le 10^6$ - 对所有 $i$（$0\le i < n$），有 $0\le s_i < 2^{31}-1$。

输出一行一个整数，表示按照上述规则，使用 Alice 的函数将输入数组 $s$ 排序所需的最小总代价。

由 ChatGPT 4.1 翻译