14300: 【原4300】中间的奶牛

题目

题目描述

author: TJH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4300

Description

助教最近热衷养奶牛，他希望知道“中间的”奶牛的产量：一半奶牛的产量大于等于该奶牛的产量；一半奶牛的产量小于等于该奶牛的产量。

给定养的N (N为奇数，且1<=N<10000)头奶牛，以及它们的产量（范围从1到1000000），助教希望你找到“中间的”奶牛的产量。

Input Format

第一行为N。

第2~N+1行：每一行是一头奶牛的产量。

Output Format

输出“中间的”奶牛的产量。

Sample Input

5
20
40
10
30
50

Sample Output

30

victrid's solution

#include <iostream>

using namespace std;

int *MergeSort(int *list, int listSize)
{
    if (listSize == 1)
        return list;
    if (listSize == 2)
    {
        if (list[0] > list[1])
        {
            int temp = list[0];
            list[0] = list[1];
            list[1] = temp;
            return list;
        }
        return list;
    }
    int *tmplist = new int[listSize];
    int *llst = MergeSort(list, listSize / 2);
    int *rlst = MergeSort(list + listSize / 2, listSize - listSize / 2);
    int lct = 0, rct = 0;
    while (lct + rct != listSize)
    {
        if ((llst[lct] <= rlst[rct] && lct < listSize / 2) || rct >= listSize - listSize / 2)
        {
            tmplist[lct + rct] = llst[lct];
            lct++;
        }
        else
        {
            tmplist[lct + rct] = rlst[rct];
            rct++;
        }
    }
    for (int i = 0; i < listSize; i++)
    {
        list[i] = tmplist[i];
    }
    return list;
}
int main()
{
    int n;
    cin >> n;
    int *cnlist = new int[n];
    for (int i = 0; i < n; i++)
        cin >> cnlist[i];
    MergeSort(cnlist, n);
    cout << cnlist[n / 2];
    return 0;
}

Zsi-r's solution

#include <iostream>

using namespace std;

int divide(int a[],int low,int high)
{
    int k = a[low];
    do
    {
        while(low<high&&a[high]>=k)
            high--;
        if(low<high)
            a[low++] = a[high];
        while(low<high&&a[low]<=k)
            low++;
        if (low<high)
            a[high--] = a[low];
    } while (low != high);
    a[low] = k;
    return low;
}

void quickSort(int a[],int low,int high)
{
    int mid;
    if (low>=high)//只有1个或0个元素
        return;
    mid = divide(a, low, high);
    quickSort(a, low, mid-1);
    quickSort(a, mid + 1, high);
}

void quickSort(int a[],int size)
{
    quickSort(a, 0, size - 1);
}

int main()
{
    int N ,*array;
    cin >> N;
    array = new int[N];
    for (int i =0;i<N;i++)
    {
        cin >> array[i];
    }
    quickSort(array, N);
    cout << array[N / 2];
    return 0;
}