首页 > 专题系列 > Java解POJ > POJ 2388 Who’s in the Middle [解题报告] Java
2013
11-11

POJ 2388 Who’s in the Middle [解题报告] Java

Who’s in the Middle

问题描述 :

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.

输入:

* Line 1: A single integer N

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

输出:

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

样例输入:

5
2
4
1
3
5

样例输出:

3

温馨提示:

INPUT DETAILS:

Five cows with milk outputs of 1..5

OUTPUT DETAILS:

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

解题代码:

import java.io.BufferedInputStream; 
import java.util.Scanner; 
public class Main{ 

    public static void main(String[] args) { 
        Scanner scan = new Scanner(new BufferedInputStream(System.in)); 
        if (scan.hasNext()) { 
            int n = scan.nextInt(); 
            int[] array = new int[n + 1]; 
            for (int i = 0; i < n; i++) { 
                array[i + 1] = scan.nextInt(); 
            } 
            quickSort(array); 
            System.out.println(array[n / 2 + 1]); 

        } 
    } 

    private static int partition(int[] array, int low, int high) { 
        int key = array[low]; 
        while (low < high) {
            while (low < high && array[high] >= key) {
                high--; 
            } 
            array[low] = array[high]; 
            while (low < high && array[low] <= key) {
                low++; 
            } 
            array[high] = array[low];  
        } 
        array[low] = key; 
        return low; 
    } 

    private static void qSort(int[] array, int low, int high) { 
        int pivotloc; 
        if (low < high) {
            pivotloc = partition(array, low, high); 
            qSort(array, low, pivotloc - 1); 
            qSort(array, pivotloc + 1, high); 
        } 
    } 

    public static void quickSort(int[] array) { 
        int n = array.length - 1; 
        qSort(array, 1, n); 
    } 
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。