题目名称 2926. [USACO Open18Gold]Out of Sorts
输入输出 sort_gold_18open.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 10 简单对比
题目来源 2018-11-07
开放分组 全部用户
提交状态
分类标签
通过:11, 提交:26, 通过率:42.31%
Gravatar乐孤廉居 100 0.050 s C++
Gravatar夜未央 100 0.104 s C++
Gravatar乐未疡 100 0.116 s C++
Gravatar666666666666 100 0.135 s C++
GravatarBenjamin 100 0.144 s C++
Gravatar梦那边的美好ETMN 100 0.147 s C++
Gravatarleon 100 0.153 s C++
Gravatar瑆の時間~無盡輪迴·林蔭 100 0.157 s C++
Gravatar@@@ 100 0.159 s C++
Gravatar雾茗 100 0.163 s C++
关于 Out of Sorts 的讨论
冒泡
Gravatar-1
2018-04-13 07:06 1楼
Gravatar夜未央
2018-11-07 20:54 2楼
Gravatar夜未央
2018-11-07 21:03 3楼

2926. [USACO Open18Gold]Out of Sorts

★★☆   输入文件:sort_gold_18open.in   输出文件:sort_gold_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得到一个有趣的观察现象:大的元素很快就会被拉到数组末尾,然而小的元素需要很长时间“冒泡”到数组的开头(她怀疑这就是为什么这个算法得名的原因)。为了实验和缓解这一问题,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≤N≤100,000)。接下来N行描述了A[0]…A[N−1],每个数都是一个范围为0…10^9的整数。输入数据不保证各不相同。


【输出格式】

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

【样例输入】

5
1
8
5
3
2

【样例输出】

2

【数据规模】

30%的数据N<=10000;

100%的数据N<=100000;

【来源】

USACO 2018 OPEN CONTEST Gold Problem 1

供题:Brian Dean