[2021.11.14]UPC-2021级新生个人训练赛第3场-19282 Problem D 排队

本文主要是介绍[2021.11.14]UPC-2021级新生个人训练赛第3场-19282 Problem D 排队，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

乐乐的 n 位朋友都拥有唯一的一个编号，编号分别为 1 至 n。某天按到达的时间顺序又给了一个顺序号，此时发现顺序号与多数的朋友编号不一致。乐乐想：如果俩俩交换顺序号，使得每位朋友的编号与顺序号相同，则最少需要交换几次？ 

包含二行： 
第一行只有一个正整数：n，表示乐乐朋友的人数 
第二行共有 n 个正整数，分别表示按顺序到达的朋友编号 

输出

只有一行且只有一个正整数：最少的交换次数 

样例输入 Copy

5  
4 2 1 5 3

样例输出 Copy

3

提示

对于 30%的数据，  1 <= n <= 100 
对于 80%的数据，  1 <= n <= 10 000 
对于 100%的数据， 1 <= n <= 100 000 

题解：

该题思路很清晰，但10^5的数据量和时间限制，秒杀掉了复杂度为O(n^2)的方法。

我当时以基于交换的排序思路来做，发现排序是根本逃不开O(n^2)的，而其他复杂度<O(n^2)的排序算法，却无法输出最少交换数。

解决的关键是抛开排序的思路，这个题并不是真正的排序，因为该题1~i个数是连续的。

我的做法是..：

        将不属于该位置的数与其应在位置的数进行交换，若交换后的数仍然不属于该位置，则重新读一边这句话 ，则继续进行交换 ：）

如有纰漏 请多多指正！!

代码如下

该方法时间复杂度为O(n)。

#include <cstdio>
int main() {int i,n,t,ans=0;scanf("%d",&n);int b[n+1];for(i=1;i<=n;i++){scanf("%d",&b[i]);}for(i=1;i<=n;i++){if(b[i]!=i){t=b[i]; //暂时储存该数b[i]=b[t];    //将被交换的数放在该位置b[t]=t;     //将该数放到它应在的位置ans++;    //记录交换次数i--;    //判断被交换的数是否应在该位置}}printf("%d ",ans);return 0;
}

这篇关于[2021.11.14]UPC-2021级新生个人训练赛第3场-19282 Problem D 排队的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---