高雄市98資訊學科能力競賽 第二題:數列最小值
作法 : 窮舉中位數的可能
第一程式碼-使用 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;
}