uva 10057 - A mid-summer night's dream.

Problem C
A mid-summer night’s dream
Input:standard input
Output:standard output
 
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 
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
이 문제를 풀면 중학교 수학 선생님이 생각난다. 절대적인 지식은 모두 그녀가 가르친 그리움이다.
절대치의 기하학적 의미는 두 점 사이의 거리를 대표한다.다음은 0점 분류 토론 문제로 A에서 x1에서 xn까지의 거리와 최소값을 요구합니다.
| | 수축: 1, 2...X1 ....X2...분명: x1<=A<=X2;2. | | | | | | 수축: 1, 2...X1 ....X2...X3.....X4 x1, x4 1조, x2, x3 1조의 X2<=A<=x3, min=|x4-x1|+|x3-x2|;가령 A가 x1, x2 사이, A에서 x1, x4의 거리는 |x4-x1|이고 그 X2까지 X3의 거리는 |x3-x2|A보다 다른 위치에서 동일하다.그래서 숫자 개수가 짝수일 때 A는 가장 중간에 있는 두 숫자 사이에서 값을 얻는다.            |         |       | 1 2  .. X1 ....X2...X3.... x1, x3 1조, x2 단독 1조;A=x2; A는 x1, x3 사이에서 끝점까지의 거리가 변하지 않기 때문에 x2의 가장 가까운 점은 최소값으로 할 수 있다. A=x2
4.            |          |       |          |         | 1 2  .. X1 ....X2...X3.....X4.....X5 x1, x5 1조, x2, x4 1조, x3 단독 1조 A=x3;같은 위의 A는 x1, x5 사이에서 그룹을 나눈 후의 단점 거리가 변하지 않기 때문에 x3의 가장 가까운 점은 최소값으로 할 수 있다. A=x3가 홀수일 때 A는 중위수이다.

#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,a[1000000];
int main()
{
 int i,min,max,sum,count;
 while (scanf("%d",&n)!=EOF)
 {
  for (i=0;i<n;i++)
  scanf("%d",&a[i]);
  sort(a,a+n);
  if (n%2) {sum=1;min=a[n/2]; max=min;}
      else {sum=a[n/2]-a[n/2-1]+1; min=a[n/2-1];max=a[n/2];}
  count=0;
  for (i=0;i<n;i++)
  {
   if ((a[i]>=min)&&(a[i]<=max)) ++count;
   if (a[i]>max) break;
  }
 printf("%d %d %d
",min,count,sum);
 }
 return 0;
}