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

[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.
  

sample input

6
2 6 5 6 3 5

sample output

5

Sample explanation

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

sample input

4
3 4 6 7

sample output

-1

Sample explanation

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

sample input

5
3 4 6 6 7

sample output

-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