# [CCF CSP] 201612-1 median (100 points)

## Problem description

In an integer sequence a1, a2 , an, if there is a number, the number of integers greater than it is equal to the number of integers less than it, it is called the middle number. In a sequence, there may be multiple intermediate numbers with different subscripts, and the values of these intermediate numbers are the same.
Given a sequence of integers, find the value of the middle number of the sequence.

## Input format

The first line of the input contains an integer n, which represents the number of numbers in the integer sequence.
The second line contains n positive integers, representing a1, a2 an.

## Output format

If the intermediate number of the contract sequence exists, the value of the intermediate number is output; otherwise, output - 1 means that there is no intermediate number.

6
2 6 5 6 3 5

5

## Sample explanation

There are two numbers smaller than 5 and two numbers larger than 5.

4
3 4 6 7

-1

## Sample explanation

None of the four numbers in the sequence meet the definition of the middle number.

5
3 4 6 6 7

-1

## Sample explanation

None of the five numbers in the sequence meet the definition of the middle number.

## Scale and convention of evaluation case

For all evaluation cases, 1 ≤ n ≤ 1000, 1 ≤ ai ≤ 1000.

## Code

C++

```#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void computer_min_max_sum(int &min,int &max,int middle,int n,vector<int> &number)
{
for(int i=0;i<middle;i++)
{
if(number[i]<number[middle])
min++;
}

for(int i=middle;i<n;i++)
{
if(number[i]>number[middle])
max++;
}
}

int main(int argc, char** argv) {
int n,temp,middle;
int min=0,max=0;
int result=-1;
vector<int> number;
cin>>n;

//input
for(int i=0;i<n;i++)
{
cin>>temp;
number.push_back(temp);
}
//sort
stable_sort(number.begin(),number.end());
middle=n/2;
//If it's even
if(n%2==0)
{
//The middle two have the same number
if(number[middle]==number[middle-1])
{
//Calculate less than quantity quantity more than quantity
computer_min_max_sum(min,max,middle,n,number);
if(min==max)
result=number[middle];
}
else
result=-1;
}else{//If it's an odd number
//Calculate less than quantity quantity more than quantity
computer_min_max_sum(min,max,middle,n,number);
if(min==max)
result=number[middle];
else
result=-1;
}
cout<<result;
return 0;
}```

Tags: less

Posted on Thu, 02 Apr 2020 07:38:55 -0700 by bschmitt78