题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3612
题意解析:给出一系列操作,按要求输出:1、add m,加入一个数,并输出现有数的中位数;2、remove m,从现有的数中删除数m,若现有的数中不存在m,则输出“Wrong!”,若删除m后,现有的数位空,则输出“Empty!”,否则,输出现有的数的中位数。
题目分析:注意,输入的数可能会是一个小数,并末尾带0(我认为的),但输出的数小数最后一位为非0位,这个时候我用了个sprintf()函数转化。

代码如下:

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

char str[10];
double a[10005];
int cnt;

//处理输出的数小数位最后为非0数
void Output( double s ){
    char sa[10015];
    int i,len;
    sprintf( sa, "%lf",s );
    len = strlen(sa);
    for( i=len-1; i>=0 ; i– ){
        if(sa[i] == '.')
            break;
        if( sa[i] == '0' )
            sa[i] = '\0';
        else
            break;
    }
    if( sa[ i ] == '.')
        sa[i] = '\0';
    if( sa[0] == '\0' )
        printf("0\n");
    printf( "%s\n",sa );
}
//用二分查找当前要操作的数该插入或者在当前数中的位置
int Search(double s,int k){
    int l=0,r=cnt-1,m=(l+r)/2;
    while( l <= r ){
        if( a[m] > s )
            r = m – 1;
        else
            l=m + 1;
        m = (l+r)/2;
    }
    if( k )
        return l;
    return r;
}
//添加一个数,并求中位数
void Add( double s ){
    int k = Search( s,1 );
    int i;
    for(i=cnt-1; i>=k; i–)
        a[i+1]=a[i];
    a[k] = s;
    cnt++;
    if( cnt%2 != 0 )
        Output( a[cnt/2] );
    else
        Output( (a[cnt/2]+a[(cnt-1)/2])/2 );
}
//删除一个数,并求中位数
void Remove( double s ){
    int k = Search(s,0);
    int i;
    if( k<0 || a[k]!=s )
        printf( "Wrong!\n" );
    else{
        for( i=k; i<cnt-1; i++ )
            a[i]=a[i+1];
        cnt –;
        if(cnt == 0 )
            printf("Empty!\n");
        else{
            if( cnt%2 != 0 )
                Output( a[cnt/2] );
            else
                Output( (a[cnt/2]+a[(cnt-1)/2])/2 );
        }
    }
}

int main(){
    int T,n;
    double m;
    scanf( "%d",&T );
    while( T– ){
        cnt = 0;
        scanf( "%d",&n );
        while( n — ){
            scanf( "%s%lf",str,&m );
            if( strcmp(str,"add") == 0 )
                Add( m );
            else if( strcmp(str,"remove") == 0 )
                Remove( m );
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation