头像

张家吃迟尺赤


访客:241

离线:6个月前



题目链接 106.动态中位数
迷茫的问题,求助各位大佬,对顶堆哪里出了问题??????????????????????????

错误的代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int ddui[200011],xdui[200010];
int td=0,tx=0,x;
void huan(int &a,int &b)
{
    int tem=a;a=b;b=tem;
}
void pushupd(int x)
{
    while(x/2)
    {
        int fa=x/2;
        if(ddui[fa]>ddui[x]) return;
        huan(ddui[x],ddui[fa]);
        x=x/2;
    }
}
void pushupx(int x)
{
    while(x/2)
    {
        int fa=x/2;
        if(xdui[fa]<xdui[x]) return;
        huan(xdui[fa],xdui[x]);
        x=x/2;
    }
}
void pushdownd()
{
    int x=1,son=0x3f3f3f3f;
    if(x*2<=td)
    son=x*2;
    if(x*2+1<=td)
    if(ddui[x*2]<ddui[x*2+1]) son=x*2+1;
    while(son<=td)
    {
        if(ddui[son]<ddui[x]) return;
        huan(ddui[son],ddui[x]);
        x=son;
        if(ddui[x*2]>ddui[x*2+1]) son=x*2;else son=x*2+1;
    }
}
void pushdownx()
{
    int x=1,son=0x3f3f3f3f;
    if(x*2<=tx)
    son=x*2;
    if(x*2+1<=tx)
    if(xdui[x*2]>xdui[x*2+1]) son=x*2+1;
    while(son<=tx)
    {
        if(xdui[son]>xdui[x]) return;
        huan(xdui[son],xdui[x]);
        x=son;
        if(xdui[x*2]<xdui[x*2+1]) son=x*2;else son=x*2+1;
    }
}
int main()
{
    int n,x,t,ta=0,ans[100001];
    cin>>t;
    for(int j=1;j<=t;++j)
    {
        int a;
        cin>>a>>n;
        td=0,tx=0,ta=0;
        for(int i=1;i<=n;++i)
        {
            cin>>x;
            ddui[++td]=x;
            pushupd(td);
            while(td-tx>1)
            {
                huan(ddui[1],ddui[td]);
                xdui[++tx]=ddui[td];--td;
                pushdownd();
                pushupx(tx);
            }
            if(td>=1&&tx>=1)
            if(ddui[1]>xdui[1])
            {
                huan(ddui[1],xdui[1]);
                pushdownx();
            }
            if(i%2)
            {
                ans[++ta]=ddui[1];
            }
        }
        cout<<a<<' '<<ta<<endl;
        int i=1;
        for(;i<=ta;++i)
        {
            cout<<ans[i]<<' ';
            if(!(i%10)) cout<<endl;
        }
        if(j==t) return 0;
        if(i%10)
        cout<<endl;
    }
    return 0;
}






活动打卡代码 AcWing 107. 超快速排序

//求助各位大佬,为什么WA了?
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int ddui[200011],xdui[200010];
int td=0,tx=0,x;
void huan(int &a,int &b)
{
    int tem=a;a=b;b=tem;
}
void pushupd(int x)
{
    while(x/2)
    {
        int fa=x/2;
        if(ddui[fa]>ddui[x]) return;
        huan(ddui[x],ddui[fa]);
        x=x/2;
    }
}
void pushupx(int x)
{
    while(x/2)
    {
        int fa=x/2;
        if(xdui[fa]<xdui[x]) return;
        huan(xdui[fa],xdui[x]);
        x=x/2;
    }
}
void pushdownd()
{
    int x=1,son=0x3f3f3f3f;
    if(x*2<=td)
    son=x*2;
    if(x*2+1<=td)
    if(ddui[x*2]<ddui[x*2+1]) son=x*2+1;
    while(son<=td)
    {
        if(ddui[son]<ddui[x]) return;
        huan(ddui[son],ddui[x]);
        x=son;
        if(ddui[x*2]>ddui[x*2+1]) son=x*2;else son=x*2+1;
    }
}
void pushdownx()
{
    int x=1,son=0x3f3f3f3f;
    if(x*2<=tx)
    son=x*2;
    if(x*2+1<=tx)
    if(xdui[x*2]>xdui[x*2+1]) son=x*2+1;
    while(son<=tx)
    {
        if(xdui[son]>xdui[x]) return;
        huan(xdui[son],xdui[x]);
        x=son;
        if(xdui[x*2]<xdui[x*2+1]) son=x*2;else son=x*2+1;
    }
}
int main()
{
    int n,x,t,ta=0,ans[100001];
    cin>>t;
    for(int j=1;j<=t;++j)
    {
        int a;
        cin>>a>>n;
        td=0,tx=0,ta=0;
        for(int i=1;i<=n;++i)
        {
            cin>>x;
            ddui[++td]=x;
            pushupd(td);
            while(td-tx>1)
            {
                huan(ddui[1],ddui[td]);
                xdui[++tx]=ddui[td];--td;
                pushdownd();
                pushupx(tx);
            }
            if(td>=1&&tx>=1)
            if(ddui[1]>xdui[1])
            {
                huan(ddui[1],xdui[1]);
                pushdownx();
            }
            if(i%2)
            {
                ans[++ta]=ddui[1];
            }
        }
        cout<<a<<' '<<ta<<endl;
        int i=1;
        for(;i<=ta;++i)
        {
            cout<<ans[i]<<' ';
            if(!(i%10)) cout<<endl;
        }
        if(j==t) return 0;
        if(i%10)
        cout<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 106. 动态中位数

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int ddui[200011],xdui[200010];
int td=0,tx=0,x;
void huan(int &a,int &b)
{
    int tem=a;a=b;b=tem;
}
void pushupd(int x)
{
    while(x/2)
    {
        int fa=x/2;
        if(ddui[fa]>ddui[x]) return;
        huan(ddui[x],ddui[fa]);
        x=x/2;
    }
}
void pushupx(int x)
{
    while(x/2)
    {
        int fa=x/2;
        if(xdui[fa]<xdui[x]) return;
        huan(xdui[fa],xdui[x]);
        x=x/2;
    }
}
void pushdownd()
{
    int x=1,son;
    if(ddui[x*2]>ddui[x*2+1]) son=x*2;else son=x*2+1;
    while(son<=td)
    {
        if(ddui[son]<ddui[x]) return;
        huan(ddui[son],ddui[x]);
        x=son;
        if(ddui[x*2]>ddui[x*2+1]) son=x*2;else son=x*2+1;
    }
}
void pushdownx()
{
    int x=1,son;
    if(xdui[x*2]<xdui[x*2+1]) son=x*2;else son=x*2+1;
    while(son<=tx)
    {
        if(xdui[son]>xdui[x]) return;
        huan(xdui[son],xdui[x]);
        x=son;
        if(xdui[x*2]<xdui[x*2+1]) son=x*2;else son=x*2+1;
    }
}
int main()
{
    while(~scanf("%d",&x))
    {
        td=0,tx=0;
        ddui[++td]=x;
        while(scanf("%d",&x)&&x!=0)
        {
            while(td<tx)
            {
                huan(xdui[1],xdui[tx]);
                ddui[++td]=xdui[tx--];
                pushdownx();
                pushupd(td);
            }
            if(x==-1)
            {
                printf("%d\n",ddui[1]);
                huan(ddui[1],ddui[td]);
                --td;
                pushdownd();
                continue;
            }
            ddui[++td]=x;
            pushupd(td);
            while(td-tx>1)
            {
                huan(ddui[1],ddui[td]);
                xdui[++tx]=ddui[td];--td;
                pushupx(tx);
            }
            if(td>=1&&tx>=1)
            if(ddui[1]>xdui[1])
            {
                huan(ddui[1],xdui[1]);
                pushdownx();
            }
        }
        cout<<endl;
    }
    return 0;
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~