POJ 2388 - Who's in the Middle

算法

原创

发布日期: 2011-05-12

更新日期: 2026-11-06

文章字数: 471

阅读时长: 2 分

阅读次数:

POJ 2388 - Who’s in the Middle
Time: 1000MS
Memory: 65536K
难度: 初级
分类: 排序

0x00 POJ 原题

Description

FJ is surveying his herd to find the most average cow. He wants to know how much milk this ‘median’ cow gives: half of the cows give as much or more than the median; half give as much or less.

Given an odd number of cows N (1 <= N < 10,000) and their milk output (1..1,000,000), find the median amount of milk given such that at least half the cows give the same amount of milk or more and at least half give the same or less.

Input

* Line 1: A single integer N

* Lines 2..N+1: Each line contains a single integer that is the milk output of one cow.

Output

* Line 1: A single integer that is the median milk output.

Sample Input

Sample Output

Hint

INPUT DETAILS:

Five cows with milk outputs of 1..5

OUTPUT DETAILS:

1 and 2 are below 3; 4 and 5 are above 3.

Source

USACO 2004 November

0x10 题目概述

给定 n 个数，输出中间值（注意不是求平均）。

0x20 解题思路

可以用 sort，干脆快捷，但是注意排序起止位置。

也可以用 quicksort，(最好用随机快排，尝试一下 srand 和 rand)。

没什么要注意的水题，不过真要注意的话，就不要用冒泡、插入、选择排序之类的 O(n^2)算法，1W 个数铁定超时。

0x30 测试数据

输入：input
输出：output

0x40 AC 源码

//Memory  Time
//292K    47MS  

#include<iostream>
#include<iomanip>
#include<algorithm>
using namespace std;

int main(void)
{
    int n;
    while(cin>>n)
    {
        int* milk=new int[n+1];

        for(int i=1;i<=n;i++)
            cin>>milk[i];

        sort(milk+1,milk+n+1);

        cout<<milk[n/2+1]<<endl;

        delete milk;
    }
    return 0;
}