当前位置: 首页 > article >正文

【数据结构 | PTA】与零交换

将 { 0, 1, 2, …, n−1 } 的任意一个排列进行排序并不困难,这里加一点难度,要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作,将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 },我们可以通过下列操作完成排序:

Swap(0, 1) ⟹ { 4, 1, 2, 0, 3 }
Swap(0, 3) ⟹ { 4, 1, 2, 3, 0 }
Swap(0, 4) ⟹ { 0, 1, 2, 3, 4 }

本题要求你找出将前 n 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。

输入格式:
输入在第一行给出正整数 n (≤10的5次方);随后一行给出{ 0, 1, 2, …, n−1 } 的一个排列。数字间以空格分隔。

输出格式:
在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。

输入样例:
10
3 5 7 2 6 4 9 0 8 1

输出样例:
9

#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n;
ll ans, idx, flag, step;
ll a[N]; //记录每个点的数字
ll vis[N]; //记录这个点是否出现在其他环过
 
int main() {
    cin >> n;
    for (ll i = 0; i < n; i++)cin >> a[i];
    for (ll i = 0; i < n; i++) {
        if (!vis[i] && a[i] != i) {
            flag = 0;//判断这个环里是否有0
            idx = i;//环的起点
            step = 0;//记录步数
            while (!vis[idx]) {
                if (!a[idx])flag = 1;//环里有0,则 flag 标注为 1
                vis[idx] = 1;
                idx = a[idx];
                step++;
            }
            if (flag)ans += step - 1;
            else ans += step + 1;
        } else vis[i] = 1;
    }
    cout << ans << endl;
}

http://www.kler.cn/a/371175.html

相关文章:

  • [mysql]相关子查询
  • 【51 Pandas+Pyecharts | 深圳市共享单车数据分析可视化】
  • Linux高手进阶
  • 云原生笔记
  • 部署MiniCPM-V
  • 【C++单调栈】962. 最大宽度坡|1607
  • MATLAB基础应用精讲-【数模应用】PageRank(附R语言、MATLAB、Java和python代码实现)
  • 数字身份发展趋势前瞻:无密码认证
  • 哈工大《理论力学》第九版课后答案解析及笔记PDF
  • Java Lock ReentrantLock 源码
  • Redis的删除策略以及内存淘汰机制
  • 探索 Surya:一款强大的开源 OCR 工具,支持 90 多种语言识别
  • C#实现word和pdf格式互转
  • STM32中的__HAL_RCC_GPIOA_CLK_ENABLE(); 这个为什么和普通的库函数不一样,前面有两个下划线?
  • OTX系统架构分析
  • 微服务架构:解密微服务的基本概念
  • 【案例】三维物体描边
  • pyav保存视频
  • RN如何实现页面渐变背景
  • 探索 MongoDB 的奇幻世界:路由、分片与节点的三重奏
  • asp.net Core日志 ILoggerFactory、ILogger、ILoggerProvider
  • C++第4课——swap、switch-case-for循环(含视频讲解)
  • 【机器学习】环境搭建及Sklearn鸢尾花数据集
  • 字节青训营 | 数字分组求偶数和
  • 【C++指南】类和对象(五):类的默认成员函数——全面剖析 赋值运算符重载函数
  • Spring+SpringMVC+SpringJDBC搭建web项目实现商品查询