1067 Sort with Swap(0, i)
2022/2/11 23:42:34
本文主要是介绍1067 Sort with Swap(0, i),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1067 Sort with Swap(0, i)
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 (≤105) 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
#include<cstdio> #include<algorithm> using namespace std; int set[100010]; //数字的位置 int main() { int n; scanf_s("%d", &n); int temp; int left = 0; //记录除0外不在本位上的数字个数 for (int i = 0; i < n; i++) { scanf_s("%d", &temp); set[temp] = i; if (temp != i&&i) left++; } int ans = 0; //交换次数 int k = 1; //记录除0外最小的不在本位上的数字 while (left) { if (set[0]) { swap(set[0], set[set[0]]); left--; ans++; } else { while (k < n) { if (set[k] != k) { swap(set[0], set[k]); ans++; break; } k++; } } } printf("%d", ans); }
这篇关于1067 Sort with Swap(0, i)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)