# PAT A1067. Sort with Swap(0,*) (25) 原

阿豪boy

https://www.patest.cn/contests/pat-a-practise/1067

Given any permutation of the numbers {0, 1, 2,..., N-1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive N (<=105) followed by a permutation sequence of {0, 1, ..., N-1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

`10 3 5 7 2 6 4 9 0 8 1`

Sample Output:

`9`

## 解题思路

``````#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;
int main() {
int n, t, c = 0;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &t);
a.push_back(t);
}
int cnt = 0;
while (c < n) { //序列排序未结束
if (0 == a[0]) { //首位为0，找出第一个未排序的数的位置
for (; c < n && c == a[c]; ++c)
continue;
if (c >= n) break;
swap(a[0], a[c]);
++cnt;
} else { //首位非0，与应处于的位置交换
swap(a[0], a[a[0]]);
++cnt;
}
}
printf("%d\n", cnt);
return 0;
}``````

http://blog.csdn.net/apie_czx/article/details/48243647

### 阿豪boy

include 2 3 static void swap(int a, int b) 4 { 5 | int tmp = *a; 6 | a = b; 7 | *b =tmp; 8 } 9 10 static int findPivot(int *a, int left, int right) 11 { 12 | int center = (int)(......

xinzaibing
2012/04/16
109
4

1、列出当前系统上所有已经登录的用户的用户名，注意：同一个用户登录多次，则只显示一次即可。 [root@localhost ~]# who root :0 2016-12-25 16:28 (:0) root tty2 2016-12-25 16:31 root ...

2016/12/25
0
0
python 使用爬虫下载京东图片

super李导
06/01
0
0
Java正则表达式问号冒号的使用

在Java和Javascript中正则表达式字符串前面加上?:表示非捕获型匹配，否则就是捕获型匹配。   捕获型括号会将匹配到的内容捕获到一些变量里，这些变量按照捕获型括号的左括号为顺序从1...

2015/09/13
1K
0
【PAT】1028. List Sorting (25)

fanfan4569
02/02
0
0
java冒泡排序中Sort.swap使用问题请教

@shugkq 你好，想跟你请教个问题： 在你的java冒泡排序中，这段代码： for (int i = array.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (array[j] > array[j + 1]) { Sort......

2015/05/20
370
2
nginx的worker进程挂起且某个CPU负载达到100%

nginx的worker进程挂起且某个CPU负载达到100% 场景说明： #tcp连接状态 [root@ ~]# netstat -nat |awk '{print \$6}'|grep -v 'Foreign'|grep -v 'established)'|sort|uniq -c|sort -rn 3010 ......

perofu
2015/07/31
0
1

2016/04/18
31
0

2012/09/19
191
0

2015/03/15
0
0

OSChina 周一乱弹 —— 你的朋友圈有点生锈了

Osc乱弹歌单（2018）请戳（这里） 【今日歌曲】 @Devoes :分享Trademark的单曲《Only Love (电视剧《妙手仁心 II》插曲)》: 《Only Love (电视剧《妙手仁心 II》插曲)》- Trademark 手机党少...

100
5
【面试题】盲人坐飞机

garkey

1
0

JandenMa

1
0
arts-week1

Algorithm 594. Longest Harmonious Subsequence - LeetCode 274. H-Index - LeetCode 219. Contains Duplicate II - LeetCode 217. Contains Duplicate - LeetCode 438. Find All Anagrams ......

yysue

1
0
NNS拍卖合约

1
0
Java IO类库之管道流PipeInputStream与PipeOutputStream

0
0
AB 压力测试

Ubuntu 安装AB apapt-get install apache2-utils 使用AB 压力测试 -c 并发数 -n请求总数 ab -c 3000 -n 10000 http://localhost/test/index.php AB只能测试localhost 返回结果 This is Apac......

xiawet

0
0

Python在数据分析中越来越受欢迎，已经达到了统计学家对R的喜爱程度，Python的拥护者们当然不会落后于R，开发了一个个好玩的数据分析工具，下面我们来看看如何使用Python，来读红楼梦，绘制小...

1
0
Java中 发出请求获取别人的数据（阿里云 查询IP归属地）

1.效果 调用阿里云的接口 去定位IP地址 2. 代码 /** * 1. Java中远程调用方法 * http://localhost:8080/mavenssm20180519/invokingUrl.action * @Title: invokingUrl * @Description: * @ret......

Lucky_Me

1
0
protobuf学习笔记

OSC_fly

0
0