F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5278. -- [Usaco2018 Open]Out of Sorts

5278: [Usaco2018 Open]Out of Sorts

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 111  Solved: 75
[Submit][Status][Discuss]

Description

留意着农场之外的长期职业生涯的可能性,奶牛Bessie开始在不同的在线编程网站上学习算法。她到目前为止最喜
欢的算法是“冒泡排序”。这是Bessie最初的对长度为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”。

Input

输入的第一行包含N。接下来N行描述了A[0]…A[N-1],每个数都是一个范围为0…10^9的整数。
输入数据不保证各不相同。
1≤N≤100,000

Output

输出“moo”被输出的次数。

Sample Input

5
1
8
5
3
2

Sample Output

2

HINT

Source

Gold

[Submit][Status][Discuss]

HOME Back