Out of Sorts

题目描述

着眼于农场之外的长期职业发展，奶牛 Bessie 开始在各种在线编程网站上学习算法。她最喜欢的两种算法是“冒泡排序”和“快速排序”，但不幸的是，Bessie 很容易把它们搞混，结果实现了一个有些奇怪的混合版本！

我们称数组 $A$ 中元素 $i$ 与 $i+1$ 之间的位置为一个“划分点”（partition point），当且仅当 $A[...i]$ 的最大值不大于 $A[i+1 \ldots]$ 的最小值。Bessie 记得快速排序需要重排数组，使其出现一个划分点，然后递归地对两侧 $A[...i]$ 和 $A[i+1 \ldots]$ 进行排序。然而，尽管她正确地注意到，一个数组中的所有划分点都可以在线性时间内确定，但她忘记了快速排序应该如何重排数组以快速制造出一个划分点！在可能成为排序算法史上最严重的算法失误中，她做出了一个不幸的决定：用冒泡排序来完成这项任务。

下面是 Bessie 对数组 $A$ 进行排序的初始实现概要。她先写了一个简单函数，执行一趟冒泡排序：

bubble_sort_pass (A) { for i = 0 to length(A)-2 if A[i] > A[i+1], swap A[i] and A[i+1] }

随后，她的 quick(ish) sort 递归代码结构如下：

quickish_sort (A) { if length(A) = 1, return do { // 主循环 work_counter = work_counter + length(A) bubble_sort_pass(A) } while (no partition points exist in A) divide A at all partition points; recursively quickish_sort each piece }

Bessie 很好奇她的代码运行速度。为简单起见，她认为主循环的每次迭代都花费线性时间，因此她在循环内相应地累加一个名为 work_counter 的全局变量，用来记录算法所做的总工作量。

给定一个输入数组，请预测该数组经过 quickish_sort 处理后，work_counter 的最终值。

输入格式

第一行输入包含 $N$（$1 \leq N \leq 100,000$）。接下来的 $N$ 行描述 $A[0] \ldots A[N-1]$，每行是一个整数，范围为 $0 \ldots 10^9$。输入元素不保证互不相同。

输出格式

输出 work_counter 的最终值。

7
20
2
3
4
9
8
7

12

提示

在该例中，我们从数组 20 2 3 4 9 8 7 开始。经过一趟冒泡排序（work counter 增加 7），得到 2 | 3 | 4 | 9 8 7 | 20，其中 | 表示一个划分点。因此，问题被分解为递归子问题：对 2、3、4 和 20 排序（每个都需要 0 的工作量），以及对 9 8 7 排序。对于子问题 9 8 7，主循环的一趟（3 单位工作量）得到 8 7 | 9，之后再对 8 7 进行最后一趟（2 单位工作量）即可完成排序。

题目来源：Brian Dean

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum