PAT_A1067#Sort with Swap(0, i)
2024-08-29 21:54:21
Source:
Description:
Given any permutation of the numbers {0, 1, 2,..., N−1}, it is easy to sort them in increasing order. But what if
Swap(0, *)
is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.
Input Specification:
Each input file contains one test case, which gives a positive N (≤) followed by a permutation sequence of {0, 1, ..., N−1}. All the numbers in a line are separated by a space.
Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
Sample Input:
10
3 5 7 2 6 4 9 0 8 1
Sample Output:
9
Keys:
Code:
/*
Data: 2019-07-22 19:54:12
Problem: PAT_A1067#Sort with Swap(0, i)
AC: 29:14 题目大意:
排序,只能交换0和任意其他数,给出需要的最少步数 基本思路:
1.0在几号位就跟相应的数字换位置,每次操作可以将一个数字归位;
2.若0回到了0号位,则再与任意一个不在自己位置上的数字交换;
3.重复第一步,直至所有数字都归位;
*/ #include<cstdio>
#include<algorithm>
using namespace std;
const int M=1e5+;
int pos[M]; int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("Test.txt", "r", stdin);
#endif int n,num,left=,cnt=,st=;
scanf("%d", &n);
for(int i=; i<n; i++)
{
scanf("%d", &num);
pos[num]=i;
if(num!=i && num!=)
left++;
}
while(left!=)
{
if(pos[]==){
for(int i=st; i<n; i++){
if(pos[i]!=i){
swap(pos[],pos[i]);
st=i;break;
}
}
cnt++;
}
swap(pos[],pos[pos[]]);
cnt++;
left--;
}
printf("%d", cnt); return ;
}
最新文章
- 【C#】MVC项目中搭建WebSocket服务器
- [C#对Oracle操作]C#操作调用Orcale存储过程有参数
- POJ 2031 Building a Space Station
- win10 + VS2015 + EF6 + MySQL
- mysql创建/删除表的例子
- tornado解析http body的过程分析
- ReactNative 踩坑小计
- sharedevelop iis express
- IPAD之分割视图 SplitViewController
- Robot Framework自动化测试(二)第一个用例
- Day04 - Python 迭代器、装饰器、软件开发规范
- ashx页面中context.Session[";xxx";]获取不到值的解决办法
- hdu1507 Uncle Tom&#39;s Inherited Land* 二分匹配
- Java 第二周总结
- Lab 10-2
- Git Extensions 和 Tortoisegit 到底是什么?Git For VS(Git For Visual Studio)(Visual Studio 中使用 Git)
- VAE (variational autoencoder)
- LINQ 查询
- C# ListView用法
- DLL入门