记录编号	218940	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1699.中位数	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	2.192 s
提交时间	2016-01-12 14:40:17	内存使用	0.67 MiB

#include <cstdio>
#include <cstring>


#define max 50000
#define m1 100000 //定义 m1 m2 就不会再后面写错了，少写0之类的错误就不会出现了
#define m2 20000000

int a[100001]={0};//分区，计数用
int main(int argc,char **argv)
{
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
    int n;
    scanf("%d",&n);
    int i;int tmp;int M;
	int pre;//前面一个亦数字的区域
	int zhz = (n+1)>>1;//保存中间值的位置
    for(i=1;i<=n;i++){
        scanf("%d",&tmp);
        a[(tmp+m2)/m1]++;
    }
    tmp=0;pre=0;
    for(i=0;i<=400;i++){
		pre = tmp;
        tmp += a[i];
        if(tmp >= zhz)
            break;

    }
    // 这时候 i 就是中间的那个值 所在区间的编号
    // (i-200)*m10+99999
    memset(a,0,sizeof(a));
	fclose(stdin);
	
	
	freopen("median.in","r",stdin);
	// 再读取一遍
	scanf("%d",&n);
    
    int j;int k;
    for(j=1;j<=n;j++){
        scanf("%d",&tmp);
        k = (tmp+m2)/m1;//如果 tmp/m1+200 就是错的 因为有负数
        if( k==i) // 如果是这个区域的数字
        {
            a[tmp-i*m1+m2]++;//每个数字对应 1 -- 100000 每个区间的开头是: i*10W-2KW 
        }
    }
    //j=tmp -i*m1+m2 -- > tmp = j+i*m1-m2
	if(n & 1)//10 偶  01奇
    {
        j=0;
        M=pre+a[0];
        while(M < zhz){
            j++;
            M+=a[j];
        }
        printf("%0.1lf",(double)j+i*m1-m2);
        return 0;
    }
	else//奇数
	{
		j=0;
		M=pre+a[0];
		while(M < zhz){
			j++;
			M+=a[j];
		}
		if(M==zhz) //正好
		{
			pre=j;
			for(j=j+1;j<100000;j++)//向后面找不为0的数
				if(a[j]!=0)
					break;
			printf("%0.1lf",(j+i*m1-m2 + pre+i*m1-m2)/2.0);
			return 0;
		}
		else//M  > zhz
			printf("%0.1lf",(double)j+i*m1-m2);
	}
	
    return 0;
}