交换位置
测试数据来自 nnu_contest/1177
描述
有N枚硬币,编号为1~N,按照1~N排列。某天,调皮的小邹打乱了硬币的顺序,现在请你帮忙,至少需要交换几次可以使硬币的排列顺序恢复到1~N。每次交换指的是拿起两枚硬币,然后交换他们的位置。比如有5个硬币:2 1 3 5 4 ,每次拿起2个硬币,交换它们的位置,对于这么简单的情况,显然,至少需要交换2次(1与2交换,5与4交换)就可以复位。
格式
输入格式为两行:
第一行: 一个正整数N(N<10000), 表示硬币的数目
第二行:N个正整数,用空格分开,表示硬币被打乱后的排列顺序。
输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。
样例
输入样例1
5
3 1 2 5 4
输出样例1
3
输入样例2
5
5 4 3 2 1
输出样例2
2
约定
内存消耗 < 256M
用时 < 1s
提示
此题测试数据规模较小,暴力法也能过哦
信息
- ID
- 1210
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 7
- 已通过
- 1
- 通过率
- 14%
- 上传者