摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 窮舉中位數的可能

第一程式碼-使用 Counting sort

第二程式碼-使用 Quick sort

使用優化輸入  加快其速度

/***************************************************************/

#include <stdlib.h>  
#include <stdio.h>  

int input()     
{     
  char cha;     
  int x=0;     
  while(cha=getchar())     
     if(cha!=' '&&cha!='\n') break;     
  x=cha-48;     
  while(cha=getchar())      
    {     
     if(cha==' '||cha=='\n') break;     
      x=x*10+cha-48;     
    }     
    return x;     
}  
 
short num[1000001];  
int ANS[10001];  
main()  
{  
  int N;  
  while(scanf("%d",&N)==1)  
      {  
        int a,b,c,ap[10001]={0},topa=0;
        for(a=0;a<N;a++)  
            ap[input()]++;
        for(a=0;a<=10000;a++)
           for(b=0;b<ap[a];b++)
              num[topa++]=a;
        int MIN=2147483647,top=0,all1=0,all2=0;
         for(a=0;a<=N/2-1;a++) all1+=num[a];
         for(;a<N;a++)all2+=num[a];
        printf("A=");
          for(a=num[N/2-1];a<=num[N/2];a++)  
             {   
               int SUM=0;  
                  SUM=a*(N/2-1)-all1+all2-a*(N-N/2-1);  
               if(SUM<=MIN)  
                  {  
                     if(SUM==MIN)  
                       ANS[top++]=a;  
                     else top=0,ANS[top++]=a;  
                     MIN=SUM;  
                  }  
             }   
          for(a=0;a<top-1;a++)  
             printf("%d、",ANS[a]);  
          printf("%d\n",ANS[a]);  
      }  
   return 0;  
}

/***************************************************************/

#include <stdlib.h>  
#include <stdio.h>  
int compare( const void *a, const void*b )   
{  
    int *aa=(int*)a, *bb=(int*)b;  
    if(*aa>*bb) return 1;  
    if(*aa==*bb) return 0;  
    if(*aa<*bb) return -1;  
}   
int input()     
{     
  char cha;     
  int x=0;     
  while(cha=getchar())     
     if(cha!=' '&&cha!='\n') break;     
  x=cha-48;     
  while(cha=getchar())      
    {     
     if(cha==' '||cha=='\n') break;     
      x=x*10+cha-48;     
    }     
    return x;     
}  
 
 
int num[1000001];  
int ANS[10001];  
main()  
{  
  int N;  
  while(scanf("%d",&N)==1)  
      {  
        int a,b,c;  
        for(a=0;a<N;a++)  
            num[a]=input();  
        qsort(num,N,sizeof(int),compare);  
        int MIN=2147483647,top=0,all1=0,all2=0;
         for(a=0;a<=N/2-1;a++) all1+=num[a];
         for(;a<N;a++)all2+=num[a];
        printf("A=");
          for(a=num[N/2-1];a<=num[N/2];a++)  
             {   
               int SUM=0;  
                  SUM=a*(N/2-1)-all1+all2-a*(N-N/2-1);  
               if(SUM<=MIN)  
                  {  
                     if(SUM==MIN)  
                       ANS[top++]=a;  
                     else top=0,ANS[top++]=a;  
                     MIN=SUM;  
                  }  
             }   
          for(a=0;a<top-1;a++)  
             printf("%d、",ANS[a]);  
          printf("%d\n",ANS[a]);  
      }  
   return 0;  
}