轻院：2214: 小明防AK

http://acm.zzuli.edu.cn/problem.php?id=2214点击打开链接

[提交][状态][讨论版][命题人:541607120101]

题目描述

    小明做为体育委员，要给n位同学们进行排位，现在n位同学已经站成一排了，但小明有强迫症，参差不齐的看着很难受，所以小明决定将同学们按身高进行排序，排成身高有序的队列，小明想知道最多有多少同学可以不用调换位置，聪明的你能帮帮他吗？

输入

多实例输入。

每个样例第一行输入一个n，表示人数，

第二行输入n个数，表示原队列每位同学的身高 , 身高数据均在int范围内。

(1<= n <= 1000)

输出

对于每组样例，输出一个数，表示最多有多少同学可以不用调换位置就能将原队列排成身高有序的。

样例输入

10
1 2 3 4 5 6 7 8 10 9
10
10 9 8 7 6 5 4 3 2 1

样例输出

8
10

防AK是不可能防AK的，这里借用了一下c++中sort排序，很快就能做出来

#include<iostream>
#include<algorithm>
#include<stdio.h>
#define N 1020
using namespace std;
int main()
{
	int a[N],ans[N],n,max,min,i,j;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
			ans[i]=a[i];
		}
		sort(ans,ans+n);
		j=n-1;
		max=0;min=0;
		for(i=0;i<n;i++)
		{
			if(ans[i]==a[i])
				max++;
			if(ans[i]==a[j])
				min++;
			j--;
		}	
		if(min>max)
			max=min;
		printf("%d
",max);
	}
	return 0;
}