题目名称 3043. [USACO Open18Silver]Out of Sorts
输入输出 sort_silver_18open.in/out
难度等级 ★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 程远洋 2018-11-03
开放分组 全部用户
提交状态
分类标签
通过:9, 提交:27, 通过率:33.33%
Gravatarwither 100 0.107 s C++
GravatarBenjamin 100 0.123 s C++
Gravatar雾茗 100 0.164 s C++
Gravatar梦那边的美好ETMN 100 0.192 s C++
Gravatarleon 100 0.240 s C++
Gravatar瑆の時間~無盡輪迴·林蔭 100 0.240 s C++
GravatarShallowDream雨梨 100 0.244 s C++
Gravatar@@@ 100 0.247 s C++
Gravatar@@@ 100 0.260 s C++
Gravatar。。。。。 100 0.316 s C++
关于 Out of Sorts 的讨论

3043. [USACO Open18Silver]Out of Sorts

★☆   输入文件:sort_silver_18open.in   输出文件:sort_silver_18open.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】


留意着农场之外的长期职业生涯的可能性,奶牛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”。


【输入格式】

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

【输出格式】

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

【样例输入】

5
1
5
3
8
2

【样例输出】

4

【数据规模】

40%的数据N<=10000;
60%的数据N<=100000;
80%的数据大小顺序时混乱的;

【来源】

USACO 2018 OPEN CONTEST Silver Problem 1

供题:Brian Dean