P6931: 冒泡排序

---

【题目描述】

【题目描述】
留意着农场之外的长期职业生涯的可能性，奶牛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的代码会输出多少次“moo”。
【输入格式】（sort.in）：
输入的第一行包含N（1≤N≤100,000）。接下来N行描述了A[0]…A[N−1]，每个数都是一个范围为0…10^9的整数。输入数据不保证各不相同。
【输出格式】（sort.out）：
输出“moo”被输出的次数。
【输入样例】：
5
1
5
3
8
2
【输出样例】：
4
 

题目类型~

USACO-2018-银-公开赛 

咻咻~

提交答案 状态 返回