NC15892. 排队排队排队
描述
ACM竞赛队内要开运动会啦！！！！
竞赛队内的一群阳光乐观积极的队员们迅速的在操场上站成了一支队伍准备开始热身运动。但教练看了一眼觉得队伍高高低低很不整齐。
教练想让大家从低到高站好，每次教练可以任选择一个人令他走到队首，教练想知道他要最少要进行几次这样的操作才能把队伍按从低到高排整齐(身高最低的人站在队首)。
输入描述
第一行输入N（N<=1000）代表一共有N个队员
第二行输入N个数表示初始时的队伍所对应的每个人的身高（100<=身高<=300）（第一个输入的是队首，最后一个输入的是队尾）
输出描述
输出教练所需要的最小操作步数
示例1
输入:
2 183 185
输出:
0
示例2
输入:
3 173 186 166
输出:
1
说明:
一次操作将站在队尾身高为166的队员放在队首就形成了166 173 186的从低到高有序队伍C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 500K, 提交时间: 2022-08-12 22:13:42
#include<bits/stdc++.h>
using namespace std;
int a[1005],b[1005],n,mx;
int main(void){
cin>>n;
int mx=0,pos=0;
for(int i=1;i<=n;i++){
cin>>a[i];b[i]=a[i];
if(mx<=a[i])mx=a[i],pos=i;
}
sort(b+1,b+1+n);
int p=n;
for(int i=pos;i>=1;i--){
if(a[i]==b[p])p--;
}
cout<<p<<endl;
}
C++11(clang++ 3.9) 解法, 执行用时: 19ms, 内存消耗: 620K, 提交时间: 2018-05-25 17:45:00
#include <bits/stdc++.h>
using namespace std;
int main(){
int N,s[2000],s1[2000],n;
n=0;
cin>>N;
for(int i=0;i<N;i++)
{cin>>s[i];s1[i]=s[i];}
sort(s,s+N);
int j=N-1;
for(int i=N-1;i>=0;i--)
if(s[j]==s1[i]){n++;j--;}
cout<<N-n;
}