L3-002 堆栈（30 分）-蒲公英云

L3-002 堆栈（30 分）

大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于N个元素，若N是偶数，则中值定义为第N/2个最小元；若N是奇数，则中值定义为第(N+1)/2个最小元。

输入格式：

输入第一行给出正整数N（<=10^5^）。随后N行，每行给出一个操作指令，为下列3种指令之一：

Push key\Pop\PeekMedian

其中Push表示入栈，key是不超过10^5^的正整数；Pop表示出栈；PeekMedian表示查中值。

输出格式：

对每个入栈指令，将key入栈，并不输出任何信息。对每个出栈或查中值的指令，在一行中打印相应的返回结果。若指令非法，就打印“Invalid”。

输入样例：

17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

输出样例：

Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

代码：

#include<stdio.h>  
#include<string.h>  
int s[100001],c[100001],top=0;  
int lowbit(int i)  
{  
    return i&(-i);  
}  
void update(int x,int y)  
{  
    for(int i=x;i<100001;i+=lowbit(i))  
    {  
        c[i]+=y;  
    }  
}  
int getsum(int x)  
{  
    int sum=0;  
    for(int i=x;i>=1;i-=lowbit(i))  
    {  
        sum+=c[i];  
    }  
    return sum;  
}  
void PeekMedian()  
{  
    int i=1,j=100001,k=(top+1)/2;  
    while(i<j)  
    {  
        int mind=(i+j)/2;  
        if(getsum(mind)>=k)  
        {  
            j=mind;  
        }  
        else  
        {  
            i=mind+1;  
        }  
    }  
    printf("%d\n",i);  
}  
int main()  
{  
    int i,j,n,m,k,t;  
    char operation[15];  
    scanf("%d",&n);  
    for(i=0;i<n;i++)  
    {  
        scanf("%s",operation);  
        if(strcmp(operation,"Pop")==0)  
        {  
            if(top==0)  
            {  
                printf("Invalid\n");  
            }  
            else  
            {  
                printf("%d\n",s[top-1]);  
                update(s[top-1],-1);  
                top--;  
            }  
        }  
        else if(strcmp(operation,"Push")==0)  
        {  
            scanf("%d",&s[top++]);  
            update(s[top-1],1);  
        }  
        else  
        {  
            if(top==1)  
            {  
                printf("%d\n",s[0]);  
            }  
            else if(top>1)  
            {  
                PeekMedian();  
            }  
            else  
            {  
                printf("Invalid\n");  
            }  
        }  
    }  
    return 0;  
}