【POJ 2388】Who‘s in the Middle 题解（nth_element）

描述 FJ正在调查他的牛群，寻找最普通的奶牛。他想知道这头“中位数”奶牛产奶量：一半奶牛产奶的量与中位数相同或更多；一半的人给予同样多或更少。 给定奇数头奶牛N（1<=N<10000）和它们的牛奶产量（1…1000000），求出所给牛奶的中位数，使至少一半奶牛所给的牛奶量相同或更多，至少一半奶牛的牛奶量相等或更少。

输入 *第1行：单个整数N *第2..N+1行：每行包含一个整数，即一头牛的奶产量。 输出 *第1行：牛奶产量中值的单个整数。

Sample Input 5 2 4 1 3 5 Sample Output 3 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

思路

中位数即第n / 2小的元素。

AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#define AUTHOR "HEX9CF"
using namespace std;

void read(int &x)
{
    x = 0;
    char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar())
        ;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
    {
        x = x * 10 + ch - '0';
    }
}

int main()
{
    int n;
    read(n);
    vector<int> V;
    for (int i = 0; i < n; i++)
    {
        int in;
        read(in);
        V.push_back(in);
    }
    int m = n / 2;
    nth_element(V.begin(), V.begin() + m, V.end());
    cout << V[m] << endl;
    return 0;
}