10057 - A mid-summer night's dream.

This is year 2200AD. Science has progressed a lot in two hundred years. Two hundred years is mentioned here because this problem is being sent back to 2000AD with the help of time machine. Now it is possible to establish direct connection between man and computer CPU. People can watch other people’s dream on 3D displayer (That is the monitor today) as if they were watching a movie. One problem in this century is that people have become so dependent on computers that their analytical ability is approaching zero. Computers can now read problems and solve them automatically. But they can solve only difficult problems. There are no easy problems now. Our chief scientist is in great trouble as he has forgotten the number of his combination lock. For security reasons computers today cannot solve combination lock related problems. In a mid-summer night the scientist has a dream where he sees a lot of unsigned integer numbers flying around. He records them with the help of his computer, Then he has a clue that if the numbers are (X1, X2,   …  , Xn) he will have to find an integer number A (This A is the combination lock code) such that

             

             (|X1-A| + |X2-A| + … … + |Xn-A|) is minimum.

Input

Input will contain several blocks. Each block will start with a number n (0<n<=1000000) indicating how many numbers he saw in the dream. Next there will be n numbers. All the numbers will be less than 65536. The input will be terminated by end of file.

Output

For each set of input there will be one line of output. That line will contain the minimum possible value for A. Next it will contain how many numbers are there in the input that satisfy the property of A (The summation of absolute deviation from A is minimum). And finally you have to print how many possible different integer values are there for A (these values need not be present in the input). These numbers will be separated by single space.

Sample Input:

2
10
10
4
1
2
2
4

Sample Output:

10 2 1
2 2 1

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=998

---

這一題也是和中位數有相關的題目。題目是說有一堆數字X1 X2 ... Xn，可以找到數字A使得(|X1-A| + |X2-A| + … … + |Xn-A|)的值是最小的，A這個數字其實就是中位數。

至於題目的output是要你輸出三個結果，第一個是最小值的A，第二個是在全部的數字中幾個數字符合A的性質，第三個是要你算出有幾個不同符合A性質的數字，這些數字包含沒有出現在這堆數字裡面的。

首先，先將題目給的所有數字做排序，若全部數字的數量是奇數，則第一個答案就是中位數，若全部數字的數量是偶數，則第一個答案就是中間兩個數中的第一個數字(因為第一個答案要求的是最小值的A)。接下來要求出第二個答案，若全部數字的數量是奇數，則第二個答案就是所有和中位數相等的數字，若全部數字的數量是偶數，則第二個答案就是所有和中間兩個數相等的數字。最後是第三個答案，若全部數字的數量是奇數，則第三個答案就是1(因為只會有那一個，沒有其他不一樣數字的可能)，若全部數字的數量是偶數，則第三個答案就是中間兩數相減加1，因為除了中間兩個數以外，兩數中間每個不同的值都包含在內。

以下是c++程式碼:

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

int main() {
    int n;

    while (cin >> n) {
        vector<int> nums;
        int mid;
        int countMid = 0;
        int diffValNum;

        while (n--) {
            int theNum;

            cin >> theNum;
            nums.push_back(theNum);
        }
        sort(nums.begin(), nums.end());
        mid = (nums.size() - 1) / 2;
        if (nums.size() % 2) {
            for (int i=mid; i>=0 && nums[i]==nums[mid]; i--)
                countMid++;
            for (int i=mid+1; i<nums.size() && nums[i]==nums[mid]; i++)
                countMid++;
            diffValNum = 1;
        }
        else {
            for (int i=mid; i>=0 && nums[i]==nums[mid]; i--)
                countMid++;
            for (int i=mid+1; i<nums.size() && nums[i]==nums[mid+1]; i++)
                countMid++;
            diffValNum = nums[mid+1] - nums[mid] + 1;
        }
        cout << nums[mid] << " " << countMid << " " << diffValNum << endl;
    }

    return 0;
}