PAT Advanced 1067

1067. Sort with Swap(0,*) (25)

时间限制

100 ms

内存限制

32000 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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

关于这道题,首先要注意的是swap函数只能用swap(0,*),而不是平常我们用的swap(i,j),也是这个原因,第一次做怎么做都是答案错误。

其次来说一下这道题的思路:

题目暗示的swap次数最少,言外之意就是中间没有过多的过渡交换(指的就是中间某个位置的元素多次为其他位置的元素交换做过渡,

典型的像 汉诺塔问题)。看示例{4, 0, 2, 1, 3},正常路线就是,4放到a[4]这个位置,就必须把3放到a[3]的位置,就必须把1放到a[1]的位置,

然后逆置过来就是 swap(0,1) -->swap(0,3)-->swap(0,4),说白了就是一个交换链。可以发现我们访问元素4次(2已经就位),交换3次。如果

整个链路中没有0怎么办(0已经就位),我们就需要将0重新调入到链路中来完成交换,这样交换次数应该为n+1次(增加两次0的换入和换出)。

具体代码如下:

#include <stdio.h>
#define MAX 100005
int a[MAX];
int visit[MAX];

int dfs(int x)
{
	int count=0;
	while(!visit[x])
	{
		visit[x]=1;
		count++;
		x=a[x];
	}
	return count;
}

int main()
{
	int n,j;
	scanf("%d",&n);
	for(j=0;j<n;j++)
		scanf("%d",&a[j]);

	int result=0;

	for(j=0;j<n;j++)
	{
		int count=dfs(j);
		if(count !=1 && count !=0)
			result += count+1;
	}

	/* 假设所有的环路中都不含0,这是都是默认的count+1次 */
	/* 在判断一下是否0会出现在某一个环中 */
	if(a[0]!=0)
		result -= 2;

	printf("%d",result);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏iOS122-移动混合开发研究院

【自问自答】关于 Swift 的几个疑问

感觉自己给自己释疑,也是一个极为有趣的过程。这次,我还新增了“猜想”一栏,来尝试回答一些暂时没有足够资料支撑的问题。 Swift 版本是:4.0.3。不同版本的...

33160
来自专栏XAI

【人工智能】动物、植物、车型、菜品、LOGO识别示例代码

图像识别部分接口Java-API调用示例代码 https://gitee.com/xshuai/ai/不是完整的web项目大家没必要下载运行。复制|下载相关代码...

897110
来自专栏源码之家

word如何自动分割成多个文档

47450
来自专栏后端沉思录

SpringMVC启动加载、请求分析

DispatcherServlet其实是一个Servlet,用于初始化各个功能的实现类,比如异常处理、视图处理、请求映射等;且继承了FrameworkServl...

13230
来自专栏wannshan(javaer,RPC)

dubbo通信消息解析过程分析(1)

由于rpc底层涉及网络编程接口,线程模型,网络数据结构,服务协议,细到字节的处理。牵涉内容较多,今天就先从一个点说起。 说说,dubbo通过netty框架做传...

54560
来自专栏数据结构与算法

BZOJ1269: [AHOI2006]文本编辑器editor

Descriptio 这些日子,可可不和卡卡一起玩了,原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗? 为了明确任务目标,可可对“文本编辑器...

30170
来自专栏jeremy的技术点滴

JVM的Finalization Delay引起的OOM

43280
来自专栏计算机视觉与深度学习基础

Leetcode 210 Course Schedule II 拓扑排序

There are a total of n courses you have to take, labeled from 0 to n - 1. Som...

25850
来自专栏noteless

[二十三]JavaIO之PushbackReader

PushBackReader 与 PushBackInputStream实现的原理是一样的

13420
来自专栏Java成神之路

Java微信开发_Exception_01_The type org.xmlpull.v1.XmlPullParser cannot be resolved. It is indirectly ref

这个异常是在做微信开发时出现的,在引入了XStream的jar包之后,还是出现了如下错误信息:

10930

扫码关注云+社区

领取腾讯云代金券