UVA-10057Amid-summernight'sdream.

偶数时,中位数之间的数都是能够的(包含中位数)

奇数时,一定是中位数

推导请找初中老师

#include
#include
#include
#include
#include
using namespace std;
int box[1000000];
int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int i,n,a,b,c;
    int num[65546];
    while(cin>>n)
    {
        memset(num,0,sizeof(num));
        for(i=0;i>box[i];
            num[box[i]]++;
        }
        sort(box,box+n);
        if(n%2||box[n/2-1]==box[n/2])
        {
            i=n/2;
            a=box[i];
            b=num[a];
            c=1;
        }
        else
        {
            i=n/2-1;
            a=box[i];
            b=num[box[i]]+num[box[i+1]];
            c=box[i+1]-box[i]+1;
        }
        cout< 
 
 
 UVA - 10057 
 
 
 
 
  A mid-summer night's dream. 
 
 
 
 
  
 
   
 
    
 
     
Crawling failed
 
    
 
   
 
  
 
 
 
 
 
  
Description
 
  
 
    
   
 
    
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
  
    
______________________________________________________________________________________________ Shahriar Manzoor
 16-12-2000 
 
   
 
  
 
 
 
 
 
 
Source
 Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) :: 
  Volume 4. Algorithm Design 
 
 Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: Data Structures and Libraries :: Linear Data Structures with Built-in Libraries :: 
  C++ STL algorithm (Java Collections)