L3-002 堆栈（30 分）

超、凢脫俗 2022-05-23 11:20 235阅读 0赞

大家都知道“堆栈”是一种“先进后出”的线性结构，基本操作有“入栈”（将新元素插入栈顶）和“出栈”（将栈顶元素的值返回并从堆栈中将其删除）。现请你实现一种特殊的堆栈，它多了一种操作叫“查中值”，即返回堆栈中所有元素的中值。对于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;  
    }