九度Online Judge

OJ新增积分机制,如有任何问题或者建议,请发帖到九度论坛OJ意见反馈版,祝大家一切顺利!
亲,九度OJ官方微博开通了,欢迎你来粉!微博地址:weibo.com/jobdu

 题目1398-九度Online Judge,用代码记录你的成长之路!

题目1398:移动次数

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:1649

解决:483

题目描述:

众所周知JOBDU旗下的JOBBALA公司是一家以个性、亲民著称的IT公司。在JOBBALA公司成立50周年的日子里,公司CEO组织全体员工登山旅游。按照往常的习惯,导游通常要求游客按照身高从低到高的顺序排好,但是考虑这次JOBBALA人数太多,排序很耗时间。因此,导游想了想,要求JOBBALA的员工可以随便排,但是必须保证队列的第一个是队列中最矮的,队列的最后一个是队列中最高的。例如:队列 { 1, 4, 3, 2, 2, 5} 就是符合的队列,{1, 4, 2, 3, 2, 5}也符合,而{2, 1, 2, 3, 4, 5}就是错的。请问对于任意的队列,最少要两两交换多少次,可以让其符合导游的要求?

输入:

输入有多组测试案例,每个测试案例为2行。

第一行包括一个整数n(2<=n<=200)表示人数,接下来一行包括n个整数a1, a2, …… an (1<=ai<=200) 表示n个员工初始的排列。

输出:

对应每个测试案例,按照导游的要求,输出最少需要两两交换的次数。

样例输入:
2
89 88
4
55 88 1 2
样例输出:
1
3
提示:
案例2中,最少需要移动三次:(55 88 1 2) -> (55 1 88 2) -> (1 55 88 2) -> (1 55 2 88)
答疑:
解题遇到问题?分享解题心得?讨论本题请访问:http://t.jobdu.com/thread-8121-1-1.html