松鼠排序(并查集)

简介: 松鼠排序(并查集)

松鼠排序


题目描述


松鼠宝宝有一排n个大小不一的坚果,松鼠宝宝想把坚果从小到大排序,每次他会选择两个坚果a和b每次花费1点力气把这两个坚果交换,爱动脑筋的松鼠宝宝想知道他排完这n个坚果一共需要花费的最少力气是多少?


输入描述:


第一行一个整数n代表坚果数


接下来一行n个整数代表每个坚果的大小(每个坚果大小都不一样,即大小为1-n的一个排列)


1<=n<=1e5


坚果大小x,1<=x<=n


输出描述:


一行输出代表松鼠宝宝花费的最小力气


示例1


输入


3

3 2 1


输出


1


#include<bits/stdc++.h>
using namespace std;
int a[111000];
int main()
{
  int n,t=0,s=0,u,v;
  cin>>n;
  for(int i=1;i<=n;i++)
  cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=i)
        {
            while(a[i]!=i)
            {
                swap(a[i],a[a[i]]);
                s++;
            }
        }
    }
  cout<<s;
  return 0;
}

joesx
+关注
目录
打赏
0
0
0
0
0
分享
相关文章
《手把手教你》系列基础篇(九十六)-java+ selenium自动化测试-框架之设计篇-跨浏览器(详解教程)
【7月更文挑战第14天】这篇教程介绍了如何使用Java和Selenium构建一个支持跨浏览器测试的自动化测试框架。设计的核心是通过读取配置文件来切换不同浏览器执行测试用例。配置文件中定义了浏览器类型(如Firefox、Chrome)和测试服务器的URL。代码包括一个`BrowserEngine`类,它初始化配置数据,根据配置启动指定的浏览器,并提供关闭浏览器的方法。测试脚本`TestLaunchBrowser`使用`BrowserEngine`来启动浏览器并执行测试。整个框架允许在不同浏览器上运行相同的测试,以确保兼容性和一致性。
227 3
电商平台 API 接入技术要点深度剖析
本文介绍了高效使用电商平台API的关键步骤。首先,深入理解API文档,明确功能权限与参数格式要求;其次,选择合适的接入方式,如HTTP/HTTPS协议和RESTful API;接着,实施身份验证与授权机制,确保数据安全传输;此外,还需关注性能优化、安全防护、监控与日志记录,以提升系统稳定性和响应速度;最后,进行充分测试与调试,并关注API版本更新,确保长期兼容性。
MongoDB全文检索: 助力快速精准的文本搜索
MongoDB全文检索: 助力快速精准的文本搜索
651 0
使用Docker进行微服务架构的部署
【5月更文挑战第18天】本文探讨了如何使用Docker进行微服务架构部署,介绍了Docker的基本概念,如容器化平台和核心组件,以及它与微服务的关系。通过Docker,每个微服务可独立运行在容器中,便于构建、测试和部署。文章详细阐述了使用Docker部署微服务的步骤,包括定义服务、编写Dockerfile、构建镜像、运行容器、配置服务通信、监控和日志管理以及扩展和更新。Docker为微服务提供了可移植、可扩展的解决方案,是现代微服务架构的理想选择。
如何下载远程maven仓库的jar 手动放到本地仓库?
如何下载远程maven仓库的jar 手动放到本地仓库?
1997 0
CSI指纹预处理(中值、均值、Hampel、维纳滤波、状态统计滤波器)(一)
CSI指纹预处理(中值、均值、Hampel、维纳滤波、状态统计滤波器)(一)
673 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问