# 14300: 【原4300】中间的奶牛

### 题目描述

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

## 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;
}
``````