1067 Sort with Swap(0, i) (25 分)【难度: 中 / 知识点: 置换群】
知识点 with 25 Sort swap 难度 1067
2023-09-11 14:15:52 时间
https://pintia.cn/problem-sets/994805342720868352/problems/994805403651522560
这种相关的题目见过很多次了。
常见的是只可以交换相邻两项求,有序后最少的步数。这类模型直接求逆序对即可。
还有一种模型是可以任意的交换两个数,求有序后最小的步数,答案是 n-环的个数。
本题和上面的差不多的思路,不过是加了必须通过0来交换的这一条限制。
首先,可以分析的得出,这个数组对应图的话都是一个个的环,向这种只有环的图称为置换图
- 如果这个数本身是一个自环,那么说明他已经在对应的位置了,那么直接跳过。
- 如果一个环和0在同一个环内,共有cnt个点,那么我们需要交换 cnt-1 此。
- 如果一个环没有0,且共有cnt个点,那么首先我们得先将0加进来,然后再依次交换。加入进来1次操作,cnt+1个点交换 需要cnt次 故共cnt+1次
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],st[N],n,ans;
int main(void)
{
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<n;i++)
{
if(a[i]==i) continue;//自环
if(!st[i])
{
bool flag=false;
int cnt=0;//点的个数
for(int j=i;!st[j];j=a[j])
{
if(j==0) flag=true;
cnt++;
st[j]=1;
}
if(flag) ans+=cnt-1;//和零在同一个环
else ans+=cnt+1;//和零不在同一个环
}
}
cout<<ans<<endl;
return 0;
}
相关文章
- memcache知识点梳理
- [Python] Indexing An Array With Another Array with numpy
- WPF实用知识点
- java核心知识点学习----重点学习线程池ThreadPool
- Java基础知识点汇总 三 集合
- 【BSP视频教程】STM32H7视频教程第9期:STM32H7的GPIO专题,通过驱动源码,参考手册,数据手册应用笔记系统学习GPIO知识点(2022-03-06)
- Atitit 研发体系建立 数据存储与数据知识点体系知识图谱attilax 总结
- Database之SQLSever:数据库管理人员国家职业资格证书中高级考试知识点(流式文件/封锁机制/三级模式(模式/内模式/外模式)/事务及其ACID特性/数据依赖/数据库的特点/安全/层次-网状
- 考研:研究生考试(十五天学完)之《高等数学上/下册》研究生学霸重点知识点总结之考试内容各科占比及常考知识重点梳理(函数极限连续、一元/多元函数微分学/积分学、常微分函数、向量代数与空间几何、无穷级数)
- Java程序员都要懂得知识点:反射
- java线程知识点拾遗(1)
- asp.net core 常见知识点
- JAVA之反射知识点整理