一、原题
| 试题编号： | 201612-1 |
| 试题名称： | 中间数 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
在一个整数序列
a
1,
a
2, …,
an中，如果存在某个数，大于它的整数数量等于小于它的整数数量，则称其为中间数。在一个序列中，可能存在多个下标不相同的中间数，这些中间数的值是相同的。
给定一个整数序列，请找出这个整数序列的中间数的值。
输入格式
输入的第一行包含了一个整数
n，表示整数序列中数的个数。
第二行包含 n个正整数，依次表示 a 1, a 2, …, an。
输出格式
如果约定序列的中间数存在，则输出中间数的值，否则输出-1表示不存在中间数。
样例输入
6
2 6 5 6 3 5
样例输出
5
样例说明
比5小的数有2个，比5大的数也有2个。
样例输入
4
3 4 6 7
样例输出
-1
样例说明
在序列中的4个数都不满足中间数的定义。
样例输入
5
3 4 6 6 7
样例输出
-1
样例说明
在序列中的5个数都不满足中间数的定义。
评测用例规模与约定
对于所有评测用例，1 ≤
n ≤ 1000，1 ≤
ai ≤ 1000。
|
这是一道签到题目，属于没有任何技术含量的题目，只要会用C语言，C++就都能做出来。但是，这种题目很能区分人，主要看
1.用了几分钟把题目A掉。
2.运行时间，占用空间有多低。
厉害的人，应该看一眼题目，立刻把代码输入到下面的框框中，不用编译测试，直接提交，一次通过，而且中间过程没有任何停滞和中断，整个用时取决于输入代码速度（IO速度）而不是思考速度（CPU速度）。
我比较菜，搞了得50分钟，这充分暴露了我基础不扎实这个事实，想得多而不实际有时反而会影响行动，行动力要和认知力相匹配才能发挥出最大战力，不得不承认，深度搜索型思维可以先获得一个答案，更快得到反馈，尽管这个答案未必最优。若是求解这个问题的最优太耗时，可以放弃最优，用稍次或者无修饰的算法有甚至更好的效果（对于整个刷题过程来说）。
由于刷题量少，经验不够，因此我在决策时优先队列优先级设置的不好，所以可能会思考很久（60分钟）才能AC这道简单的小题。
1、看到中间数=》中位数？
2、两层for循环暴力穷举
3、先排序，后中位数？
这就是我看到题目的第一瞬间想到的东西。
然后就开始把时间浪费在选择哪种方式上，脑中开始并行实现这三种方式，然后中位数出现了两次，于是我的思维就往中位数上跑了，跑着跑着就飞了，watchdog看不住我了，最后各种细节全部乱成一起。
其实，直接按照暴力穷举就能AC100分的，数据量不大，而且实现起来没有丝毫停滞感，一气呵成。但是，我老是在担心算法的性能问题，导致我根本就没有想去用这种暴力方法去试。这就是学了个半吊子不如少学一点，精通一些。这样还可以降低自己知识的搜索范围，尽量避免这种在没有学到大成或者圆满时耍小聪明吃大亏的事情发生。
下面附上我的第一种AC解法
暴力法：直接把题目翻译成C++代码。
对于每个输入数字，判断大于它的整数数量是否等于小于它的整数数量。=》如何得到大于它的整数数量？
对于每个输入数字arr[i]
对于每个输入数字arr[j]
如果arr[j]比arr[i]小，小于arr[i]的数量加1。
如果arr[j]比arr[i]大，大于arr[i]的数量加1。
然后遍历所有输入数字
如果大于它的整数数量等于小于它的整数数量
输出这个数字，并且结束程序。
所有可能试了一遍后，没有相等的话，就输出"-1"。
#include <iostream>
using namespace std;
int main(void){
int n;
cin>>n;
int i,j;
int arr[1005]={};
for(i=0;i<n;i++){
cin>>arr[i];
}
int couts[1005][2]={};
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(arr[j]<arr[i]){
couts[i][0]++;
}else if(arr[j]>arr[i]){
couts[i][1]++;
}
}
}
for(i=0;i<n;i++){
if(couts[i][0]==couts[i][1]){
cout<<arr[i];return 0;
}
}
cout<<"-1";
return 0;
}有空再补充更加快速和普遍的算法。