Fuzhou University OnlineJudge 
提示: 欢迎访问OurACM平台。
Problem 2291 排序

Accept: 73    Submit: 284
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

冒泡排序,想必大家都会吧!每次从左到右检查相邻的元素是否满足a[i]>a[i+1],如果满足,就交换位置i和位置i+1的元素的值,如果某次扫描整个数组之后,没有任何元素交换位置,那么排序结束。

学姐学了冒泡排序之后,研究出了一种新的排序:冒泡泡排序!这个排序方式是冒泡排序的一点小改动:每次从左到右检查连续三个值(三元组),如果满足a[i]>a[i+2],那么将这个三元组翻转一下。

比如说数组5,6,8,4,3:

第一次扫描数组:

1、 检查三元组5,6,8,由于a[i]<a[i+2],所以我们不做任何操作;

2、 检查三元组6,8,4,满足a[i]>a[i+2],翻转该三元组,数组变为5,4,8,6,3;

3、 检查三元组8,6,3,数组变为5,4,3,6,8。

第二次扫描数组:

1、 检查三元组5,4,3,数组变为3,4,5,6,8;

2、 检查三元组4,5,6,数组不发生变化;

3、 检查三元组5,6,8,数组不发生变化。

第三次扫描数组:

扫描结束后,数组与第二次扫描结束的数组一样,排序结束。

这个排序算法听起来很棒!但是聪明的学弟还是发现了一个bug:在某些情况下这个算法失效了!比如数组:5,7,6就是一个反例。

学姐现在很伤心,她想让你帮帮她:对于给定的数组,判断冒泡泡排序是否能将其正确排序,如果可以,输出“OK”;如果不行,输出第一个满足a[i]>a[i+1]的位置。

Input

多组数据。

每组数据第一行为正整数n,表示数组大小。

第二行为n个正整数,表示待排序数组。

保证所有数据不会超过int范围

n≤100000

Output

如果可以正确排序,输出“OK”,否则输出第一个满足a[i]>a[i+1]的位置(数组下标从1开始)。

Sample Input

5 5 6 8 4 3 3 8 9 7

Sample Output

OK 2

Source

福州大学第十五届程序设计竞赛_重现赛

Submit  Back  Status  Discuss