文档章节

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

 阿豪boy
发布于 2017/02/26 17:24
字数 348
阅读 13
收藏 0
点赞 0
评论 0

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

解题思路

首位为0,找出第一个未排序的数的位置进行交换 
首位非0,与该数应处的位置交换

#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

© 著作权归作者所有

共有 人打赏支持
粉丝 21
博文 971
码字总数 665601
作品 0
西安
麻烦高手帮忙看个问题,关于快速排序法

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 使用爬虫下载京东图片

首先打开京东商城-手机专栏https://list.jd.com/list.html?cat=9987,653,655&page=1&sort=sortrankasc&trans=1&JL=600#J_main 然后打开下一页https://list.jd.com/list.html?cat=9987,653,65......

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

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

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

题目 链接:https://www.patest.cn/contests/pat-a-practise/1028 Excel can sort records according to any column. Now you are supposed to imitate this function. Input Each input fi......

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
另一种快速排序

之前 http://my.oschina.net/lvyi/blog/324551 写过一种快速排序,下面是另外一种稍微不同的方法。它分别寻找比中心值 k 小和 k 大的两个元素再进行交换,逻辑更加清晰。 参考 https://clas...

兔之
2016/04/18
31
0
理解PGA(2)pga_aggregate_target详解

注: 1)pgaaggregatetarget以下简称PAT 2)我的环境: 11:42:10 sys@ORCL (^ω^) select * from v$version where rownum=1; BANNER -----------------------------------------------------......

长平狐
2012/09/19
191
0
深入JDK源码之Arrays类中的排序查找算法

二分法查找算法,算法思想:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。 基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值...

陶邦仁
2015/03/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

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

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

小小编辑
今天
100
5
【面试题】盲人坐飞机

有100位乘客乘坐飞机,其中有一位是盲人,每位乘客都按自己的座位号就坐。由于盲人看不见自己的座位号,所以他可能会坐错位置,而自己的座位被占的乘客会随便找个座位就坐。问所有乘客都坐对...

garkey
今天
1
0
谈谈神秘的ES6——(二)ES6的变量

谈谈神秘的ES6——(二)ES6的变量 我们在《零基础入门JavaScript》的时候就说过,在ES5里,变量是有弊端的,我们先来回顾一下。 首先,在ES5中,我们所有的变量都是通过关键字var来定义的。...

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拍卖合约

前言 关于NNS的介绍,这里就不多做描述,相关的信息可以查看NNS的白皮书http://doc.neons.name/zh_CN/latest/nns_background.html。 首先nns中使用的竞价货币是sgas,关于sgas介绍可以戳htt...

红烧飞鱼
今天
1
0
Java IO类库之管道流PipeInputStream与PipeOutputStream

一、java管道流介绍 在java多线程通信中管道通信是一种重要的通信方式,在java中我们通过配套使用管道输出流PipedOutputStream和管道输入流PipedInputStream完成线程间通信。多线程管道通信的...

老韭菜
今天
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绘制红楼梦词云图,竟然发现了这个!

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学习笔记

相关文档 Protocol buffers(protobuf)入门简介及性能分析 Protobuf学习 - 入门

OSC_fly
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部