首先输入正整数n,接着输入n个正整数,如果存在一个数,比该数大或比该数小的数则输出该数,如果不存在则输出-1。
这个问题可以用排序来解决,这是基础。可以证明,如果存在答案则必定所有数排序后的中间位置。
排序方法上有以下几种:
1.对n个数进行排序,找出中间那个数,然后将中间那个数的左右与其相等的数去掉,看左右剩下的数个数是否相等,如果相等则中间那个数就是答案,否在输出-1。
2.使用分治法,按照快速排序的基本思想来处理,只需要将中间的那个数找到即可。
3.使用STL的map类对数据进行排序。这种方法在同值的数据比较多时候,存储上会节省一些。
4.按照桶排序的基本思想,将相同的值放入同一个桶中,即对同值数据进行计数,然后再计算中间值。
本程序采用上述的第4种方法实现,使用一个数组valcount[]来统计各种值的数量。这样做事需要一个前提的,即数据值得范围不可以太大。本问题中“对于所有评测用例,1≤ai≤1000”,所以才是可行的。
/*CCF201612-1中间数*/
#include<iostream>
#include<cstring>
usingnamespacestd;
constintN=1000;
intvalcount[N+1];//对于所有评测用例,1≤ai≤1000
intmain()
{
intn,val;
//变量初始化:清零
memset(valcount,0,sizeof(valcount));
//输入数据,统计各个值得数量
cin>>n;
for(inti=0;i<n;i++){
cin>>val;
valcount[val]++;
}
//找出中间数
intans,mid=(n+1)/2,count=0,left;
for(inti=1;i<=N;i++)
if(count+valcount[i]>=mid){
left=count;
count=0;
ans=i;
}else
count+=valcount[i];
//输出结果
if(left==count)
cout<<ans<<endl;
else
cout<<-1<<endl;
return0;
}
上一篇:市场竞争不充分
下一篇:一个为人民服务的宗旨