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 翻译