题目:牛客幼儿园的小朋友课间操时间需要按照学号从小到大排队,但是他们太小了只能站成一列顺序却不对,现在幼儿园的阿姨需要帮忙交换小朋友的位置让他们最终有序,阿姨希望能尽快完成交换操作,问最少需要交换多少次,才能使得小朋友们从小到大排好。
注意:每个小朋友的学号不同,但是未必连续,因为可能有小朋友请假了没有来。
思路/步骤:1.创建两个数组,一个是需要排好的序列,另外一个是已经排好的序列(刚开始两个数组相等,然后用sort函数将其排好)作为交换操作的模板(因为号数不连续)。2.用for循环遍历,一旦发现两个数组不相等就将其交换直到相等(用while循环)。
注意:用lower_bound函数比用find函数更快(我当时用find不行,用lower_bound就行了)
#include "iostream" #include "algorithm" using namespace std; int main() { int N,i; cin>>N; int F[N],E[N]; for(i=0;i<N;i++){ cin>>F[i]; E[i]=F[i]; } sort(E,E+N); int end; int k=0; for(i=0;i<N;i++){ while(F[i]!=E[i]){ end=lower_bound(E, E + N, F[i]) - E; swap(F[i],F[end]); k++; } } cout<<k; }