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 (≤105)；随后一行给出{ 0, 1, 2, ..., n−1 } 的一个排列。数字间以空格分隔。
输出格式：
在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。
输入样例：
10
3 5 7 2 6 4 9 0 8 1
输出样例：
9
代码长度限制16 KB，时间限制300 ms，内存限制64 MB，栈限制8192 KB
代码：
无注释版：
#include<bits/stdc++.h>
using namespace std;
#define int long long
int v[100010];
int a[100010];
int f;
int n;
int dfs(int x){int cnt=0;if(v[x]) return cnt;v[x]=1;cnt+=dfs(a[x])+1;if(x==0) f=1;return cnt;
}
signed main(){cin>>n;int s=0;for(int i=0;i<n;i++){cin>>a[i];if(a[i]==i) v[i]=1;}for(int i=0;i<n;i++){if(v[i]) continue;f=0;int ss=dfs(i);if(f) s+=ss-1;else s+=ss+1;}cout<<s<<"\n";
} 有注释版：
#include<bits/stdc++.h>
using namespace std;#define int long long // 定义 int 为 long long 类型，用于避免大整数溢出
int v[100010]; // v 数组用来标记每个数字是否已经排序
int a[100010]; // a 数组存储输入的排列
int f; // 辅助变量，用于标记当前是否已经达到目标
int n; // 输入的排列长度// 递归函数，计算从位置 x 开始需要的交换次数
int dfs(int x){int cnt = 0; // 计数器，记录交换次数if (v[x]) return cnt; // 如果该位置已排序，返回0v[x] = 1; // 标记当前位置已处理cnt += dfs(a[x]) + 1; // 递归处理当前位置所指向的数字，并加上交换次数if (x == 0) f = 1; // 如果当前处理的是0，设置 f = 1return cnt;
}signed main() {cin >> n; // 输入排列的长度int s = 0; // 用于累计总的交换次数// 输入排列，并初始化 v 数组for (int i = 0; i < n; i++) {cin >> a[i]; // 输入每个位置的数字if (a[i] == i) v[i] = 1; // 如果该位置的数字已经在正确位置，标记为已排序}// 遍历每个位置，处理未排序的部分for (int i = 0; i < n; i++) {if (v[i]) continue; // 如果该位置已经排序，跳过f = 0; // 重置 f，用于判断是否处理了0int ss = dfs(i); // 递归计算从 i 开始需要的交换次数if (f) s += ss - 1; // 如果处理的是0，则交换次数是 ss - 1（因为最终的0交换不算）else s += ss + 1; // 否则，交换次数是 ss + 1}cout << s << "\n"; // 输出总的交换次数
}