题目:牛客幼儿园的小朋友课间操时间需要按照学号从小到大排队,但是他们太小了只能站成一列顺序却不对,现在幼儿园的阿姨需要帮忙交换小朋友的位置让他们最终有序,阿姨希望能尽快完成交换操作,问最少需要交换多少次,才能使得小朋友们从小到大排好。
注意:每个小朋友的学号不同,但是未必连续,因为可能有小朋友请假了没有来。
思路/步骤: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;
}