Out of Sorts

题目描述

为了关注农场之外的长期职业发展可能性，奶牛 Bessie 开始在各种在线编程网站上学习算法。 她目前最喜欢的算法是“冒泡排序”。下面是 Bessie 用牛码（cow-code）写的、用于排序长度为 $N$ 的数组 $A$ 的初始实现。 sorted = false while (not sorted): sorted = true moo for i = 0 to N-2: if A[i+1] < A[i]: swap A[i], A[i+1] sorted = false 显然，牛码中的“moo”命令除了打印“moo”之外什么也不做。奇怪的是，Bessie 似乎坚持要在她的代码中的不同位置加入它。 在用若干数组测试她的代码后，Bessie 得到一个有趣的观察：大的元素可以很快被拉到数组的末尾，但小的元素可能需要很长时间才能“冒泡”到数组的前面（她怀疑这就是该算法名字的由来）。为了尝试缓解这个问题，Bessie 试图修改她的代码，使得主循环的每次迭代中先向前扫描再向后扫描，这样大元素和小元素在每次主循环迭代中都有机会被拉动很长的距离。她的代码现在如下： sorted = false while (not sorted): sorted = true moo for i = 0 to N-2: if A[i+1] < A[i]: swap A[i], A[i+1] for i = N-2 downto 0: if A[i+1] < A[i]: swap A[i], A[i+1] for i = 0 to N-2: if A[i+1] < A[i]: sorted = false 给定一个输入数组，请你预测 Bessie 的修改后代码会打印多少次 “moo”。

输入格式

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

输出格式

输出打印 “moo” 的次数。

5
1
8
5
3
2

2

提示

题目来源：Brian Dean

标签: USACO|2018|Gold

来源

USACO|2018|Gold