题目描述:

体育馆里有\(n\)个人正在排队等待着上体育课，他们每个人都不一样高。
此方想要把队伍从小个子到高个子进行排序，即让队伍身高为升序。
此方每次调出一人，让此人和在他后面的人比身高，如果比对方高，则两人交换位置并和下一个人继续比较，直到比对方矮或者已经在队尾。
现在给出一个长度为\(n\)，元素为\(1\sim n\)的排列，求最少的选择次数，使队伍变为升序。

题意简述

现在给出一个长度为\(n\),元素为\(1\)到\(n\)的数组，每次选择一个元素并与下一个元素比较，若比下一个元素大就交换，直到比下一个元素小或到数组尾端,求最少的选择次数，使数组变为升序。

思路

看到题目，相信大部分人首先想到的就是冒泡排序，在数据范围较小时，但一看数据范围\(1\leq n\leq 10^6\)，而冒泡排序的最坏时间复杂度为\(O(N^2)\)，显然无法通过本题。
那我们如何使用单重\(for\)循环写出这道题呢？
我们先考虑从前往后遍历，如果选择第\(i\)个人移动，那么当他移动到当前正确的位置时，它后面的人可能也要移动，然后再把第\(i\)个人移动，反而得不偿失。
那我们考虑从后往前遍历，并用变量\(ans\)记录选择次数。
假设数组\(a\)中的最小值为\(a_n\)，因为为\(a_n\)是数组最后一个元素，本身不用操作。从\(a_{n-1}\)开始遍历整个数组，遍历到到比当前最小值大的元素就把元素更新成当前最小值。若\(a_i\)比最小值大，需要选择，\(ans+1\)，遍历完后输出\(ans\)即可。

\(AC\ \ Code\)

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],mi,ans;
int main()
{
	scanf("%d",&n);
	for(int i(1);i<=n;++i)scanf("%d",a+i);
	mi=a[n];
	for(int i(n-1);i;--i)
	{
		if(mi<a[i])a[i]=mi,++ans;
		mi=min(mi,a[i]);
	}
	printf("%d",ans);
	return 0;
}