UVa 11330 - Andy's Shoes_uva - 11330-程序员宅基地

技术标签: 解题报告  

题目:有双配对出错鞋子,要求最少的交换次数,使得鞋子配对摆放。

分析:组合数学,置换群。统计置换中循环的个数k,则结果为n-k。

            循环内部(设有m个元素)需要交换m-1次(除最后一次,每次交换最多只能有一个复位)

说明:注意鞋子的编号不一定是1~n,是1~10000之间的数字,计算时需要做映射。

#include <cstdlib>
#include <cstdio>

int value[10011];
int Lshoes[10011];
int Rshoes[10011];
int visit[10011];

int main()
{
	int t,n;
	while (~scanf("%d",&t))
	while (t --) {
		scanf("%d",&n);
		for (int i = 1; i <= n; ++ i) {
			scanf("%d%d",&Lshoes[i],&Rshoes[i]);
			visit[i] = 0;
		}
		//将数据映射到1~n 
		int id = 0;
		for (int i = 1; i <= n; ++ i)
			value[Lshoes[i]] = ++ id;
		for (int i = 1; i <= n; ++ i)
			Rshoes[i] = value[Rshoes[i]];
		//计算置换中循环的个数 
		int count = 0;
		for (int i = 1; i <= n; ++ i)
			if (!visit[i]) {
				++ count;
				visit[i] = 1;
				int now = Rshoes[i];
				while (!visit[now]) {
					visit[now] = 1;
					now = Rshoes[now];
				}
			}
		
		printf("%d\n",n-count);
	}
    return 0;
}



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/mobius_strip/article/details/46141547

智能推荐

机器学习之感知器和线性回归、逻辑回归以及SVM的相互对比-程序员宅基地

文章浏览阅读552次。线性回归是回归模型感知器、逻辑回归以及SVM是分类模型线性回归:f(x)=wx+b感知器:f(x)=sign(wx+b)其中sign是个符号函数,若wx+b>=0取+1,若wx+b<0取-1它的学习策略是最小化误分类点到超平面的距离,逻辑回归:f(x)=sigmoid(wx+b)取值范围在0-1之间。感知器和SVM的对比:它俩都是用于分类的模型,且都以s..._逻辑函数与svm、感知机区别和联系

webpack 理解 babel-polyfill 和 babel-runtime 及 babel-plugin-transform-runtime的配置-程序员宅基地

文章浏览阅读2.8k次,点赞2次,收藏4次。一:理解 babel之配置文件.babelrc 基本配置项 1. 什么是babel? 它是干什么用的? ES6是2015年发布的下一代javascript语言标准,它引入了新的语法和API,使我们编写js代码更加得心应手,比如class,let,for...of promise等等这..._8004 silly decomposeactions finalize babel-plugin-transform-es2015-block-sco

uni-app小程序,实现根据中文首字母排序功能_uniapp js-pinyin-程序员宅基地

文章浏览阅读4.2k次,点赞7次,收藏17次。描述:从后端调用接口获取所有热的姓名,将这些名字的首字母排序,然后放到对应字母下面,最终效果图如下:实现过程**总体实现的思路是:**首先调用接口,获取所有员工的姓名以及其他信息,将获取回来的中文名字转换为拼音,这里做的是转为姓名首字母大写的简写格式(比如:“张三” 转为“ZS”)这里只需要名字的第一个字的首字母,使用js的截取功能就能实现,中文转拼音这里我使用的是js-pinyin,将转换好的内容渲染到页面上。1、下载js-pinyin包npm install js-pinyin2、在mai_uniapp js-pinyin

windows 10 更新后无法使用远程桌面_remote desktop is available for these editions:-程序员宅基地

文章浏览阅读1w次。远程桌面部分服务器可以连接错误消息An authentication error has occurred. The function requested is not supported This could be due to CredSSP encryption oracle remediation. For more information, see https://go.m..._remote desktop is available for these editions:

黑马程序员_JAVA_反射-程序员宅基地

文章浏览阅读358次。一、反射技术 Java反射机制是在运行状态中,对于任意一个类,都能够知道这个类中的所有属性和方法;对于任意一个对象,都能够调用它的任意一个方法和属性;这种动态获取的信息以及动态调用对象的方法的功能称为java语言的反射机制。反射就是把Java类中的各种成分映射成相应的java类。二、Class类所有的类文件都有共同属性,所以可以向上抽取,把这些共性内容封装

SVG 保姆级入门知识详解,一篇文章带你上手!-程序员宅基地

文章浏览阅读2.1k次,点赞6次,收藏27次。SVG,即可缩放矢量图形(Scalable Vector Graphics),是一种基于 XML 的矢量图形格式,用于描述二维图形和动画。相比于基于位图的图像格式,如 PNG 和 JPEG,SVG 图像可以无限放大或缩小且不会失真。这篇文章带你了解一下SVG的魅力吧。_svg

随便推点

领扣LintCode算法问题答案-488. 快乐数_488 。 。 。 8 。 872552554545422225425225555255555417-程序员宅基地

文章浏览阅读815次。领扣LintCode算法问题答案-488. 快乐数目录488. 快乐数题解鸣谢488. 快乐数写一个算法来判断一个数是不是"快乐数"。一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可以变为1,那么这个数就是快乐数。样例 1:输入:19输出:true说明:19是一个快乐的数字1 ^ 2 + 9 ^ 2 = 828 ^ 2 + 2 ^ 2 = 686 ^ 2 + 8 ^ ._488 。 。 。 8 。 87255255454542222542522555525555541774。 ,:,。冫、、丶

Memory Model -- 06 -- 运行时数据区(五、方法区)_java内存模型5大块-程序员宅基地

文章浏览阅读189次。一、方法区 (Method Area)方法区 (Method Area) 与 Java 堆一样,是各个线程共享的内存区域,用于存储已经被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据当方法区无法满足内存分配的需求时,将会抛出 OutOfMemoryError 异常二、永久代与元空间在 Java 虚拟机规范中,只规定了方法区的概念及其作用,但并没有规..._java内存模型5大块

JAVA实验六_用java模拟向货船上装集装箱-程序员宅基地

文章浏览阅读1.4k次,点赞6次,收藏14次。JAVA实验六实验六一共四题,附上题目及完整代码。8702题目內容:建立Person类,成员变量为姓名和年龄,具有构造方法、get/set方法。创建NoAgesException类,当年龄为负数或大于200岁抛出异常IllegalArgumentException,正常输出“姓名年…龄从”,键盘输入姓名和年龄建立Person对象,测试该对象。输入输出说明:张三 300年龄数值非法李四 77李四…77代码编辑:import java.util.Scanner;class NoAges._用java模拟向货船上装集装箱

“不念过往,不畏将来”——2017年山东省第八届ACM大学生程序设计竞赛总结_2017年山东省acm程序设计大赛-程序员宅基地

文章浏览阅读627次。不念过往,不畏将来今天去参加了第八届山东ACM省赛,也是自己第一次参加正式的ACM比赛,有诸多感想。先说说去比赛的经过吧,整个大体上还是比较顺利的,青科大的志愿者也十分的负责用心(排队排的很有意思),住宿环境也还不错,但是宾馆的隔音的效果实在是有一点差,第二天比赛还算是清醒,迅速进入了状态,我们队还算顺利的A掉了I,G两个水题,然后开了两道题,一开始读错题导致错了两次,但是还好及时发现,A_2017年山东省acm程序设计大赛

IRC_tcp服务器支持irc-程序员宅基地

文章浏览阅读1.2k次。转载自 mst_beach 最终编辑 mst_beach IRC(Internet Relay Chat的缩写,“因特网中继聊天”)是一种通过网络的即时聊天方式。其主要用于群体聊天,但同样也可以用于个人对个人的聊天。 芬兰人雅尔口·欧伊卡林恁(Jarkko Oikarinen)于1988年8月创造了IRC来取代一个叫做MUT的程序。 连接方法 以连接到 FreeNode (chat.freenode.net) 上的 #wikipedia-zh 聊天室为例: 在支持 IRC 协议的浏览器地址栏中输_tcp服务器支持irc

特殊教育学校计算机教学计划,特殊教育学校七年级环境教育教学计划.doc-程序员宅基地

文章浏览阅读106次。特殊教育学校七年级环境教育教学计划特殊教育学校七年级环境教育教学计划李红榜◆学生情况分析:七年级共有学生10人,学生有一定的环保意识和环保知识,但不系统、不全面。极少开展综合实践活动。通过本册教材的学习,使他们掌握环保的有关知识,通过开展大量的实践活动,做环保的小主人。◆教学总目标1、学生了解一些生态环境问题的产生和发展,感知这些环境问题带来的危害,树立环保意识,转变浪费资源、破环环境的生活方式。...