玄关，不输出，求改

CCF___NOI @ 2024-08-14 20:40:20

#include<bits/stdc++.h>
using namespace std;
int h[5000001],h1[1000001],len1,b,c,n,m,s,x,t,u,v,len;
void up(int x){
    while(x!=1&&h[x]<h[x/2])
    {
        swap(h[x],h[x/2]);
        x/=2;
    }
}
void down(int x){
    while(h[x]>h[2*x]&&2*x<=len||h[x]>h[2*x+1]&&2*x+1<=len)
    {
        if(2*x+1>len)
        {
            swap(h[x],h[2*x]);
            x*=2;
        }
        else
        {
            if(h[x*2]<h[x*2+1])
            {
                swap(h[x],h[2*x]);
                x*=2;
            }
            else
            {
                swap(h[x],h[x*2+1]);
                x=2*x+1;
            } 
        }
    }
}

void up1(int x){
    while(x!=1&&h[x]>h[x/2])
    {
        swap(h[x],h[x/2]);
        x/=2;
    }
}
void down1(int x){
    while(h1[x]<h1[2*x]&&2*x>=len||h1[x]>h1[2*x+1]&&2*x+1>=len)
    {
        if(2*x+1<len)
        {
            swap(h1[x],h1[2*x]);
            x*=2;
        }
        else
        {
            if(h1[x*2]>h1[x*2+1])
            {
                swap(h1[x],h1[2*x]);
                x*=2;
            }
            else
            {
                swap(h1[x],h1[x*2+1]);
                x=2*x+1;
            } 
        }
    }
}
int main(){
    cin>>n;
    for(int i=1,op,x;i<=n;i++){
        cin>>x;
        len1++;
        h1[len1]=x;
        up1(len1);
        if(i%2==1)
        {
            while(len1&&len&&h1[1]>h[1])
           {
               len++;
               h[len]=h1[i];
               up(len);

               swap(h1[1],h1[len1]);
               len1--;
               down1(1);
           }
           while(len1>len)
           {
               len++;
               h[len]=h1[i];
               up(len);

               swap(h1[1],h1[len1]);
               len1--;
               down1(1);
           }
           while(len1>len-1)
           {
               len++;
               h[len]=h1[i];
               up(len);

               swap(h1[1],h1[len1]);
               len1--;
               down1(1);
           }
                cout<<h[1]<<endl;
        }
    }
    return 0;
}

by guanzisheng2 @ 2024-08-14 20:43:07

https://www.luogu.com.cn/discuss/869490

by guanzisheng2 @ 2024-08-14 20:47:10

你只考虑了n是奇数，n可以是偶数，我也再改，老师当时给我们讲的是对的

by CCF___NOI @ 2024-08-14 20:48:20

@xuruizhe150711 设么意思

by Malkin_Moonlight @ 2024-08-14 20:50:10

@CCF___NOI 用堆

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define endl '\n'
#define pb emplace_back
const ll MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll dx[] = {0, 0, 1, -1};
const ll dy[] = {1, -1, 0, 0};

ll n, mid;
ll a[MAXN]; 
priority_queue<ll> pq1; //大根堆 
priority_queue<ll, vector<ll>, greater<ll> > pq2; //小根堆 

int main()
{
    //输入 
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    //先处理第一个 
    mid = a[1];
    cout << mid << endl;
    //再从第二个开始 
    for (int i = 2; i <= n; i++)
    {
        //按规则处理a[i] 
        if (a[i] < mid) pq1.push(a[i]);
        else if (a[i] > mid) pq2.push(a[i]);
        if (pq1.size() != pq2.size())
        {
            //第3种情况 
            while (pq1.size() < pq2.size())
            {
                pq1.push(mid);
                mid = pq2.top();
                pq2.pop();
            }
            //第4种情况 
            while (pq1.size() > pq2.size())
            {
                pq2.push(mid);
                mid = pq1.top();
                pq1.pop();
            }
        }
        //判断是奇数个后输出 
        if (i % 2 == 1) cout << mid << endl;
    }
    return 0;
}
//思路 
/*
对顶堆算法
实现该算法需要一个大根堆pq1，一个小根堆pq2，一个变量mid初始值为a[1] 

1.用一个变量mid来保存目前的中位数，一个大根堆保存比mid小的数，一个小根堆保存比mid大的数 
2.每次读取两个数，跟mid比较，插入对应的堆里，如果发现两堆元素数量不相等，则调整
3.如果A堆比B堆多，mid插入B中，A堆堆顶弹出变成新的mid 
4.如果B堆比A堆多，mid插入A中，B堆堆顶弹出变成新的mid 
*/

by guanzisheng2 @ 2024-08-14 20:50:28

你想想，n是偶数的话，会咋样

by guanzisheng2 @ 2024-08-14 20:57:58

@guanhetian 我们老师没教优先队列，QAQ

by Malkin_Moonlight @ 2024-08-14 20:59:02

@xuruizhe150711 那你们用的什么，没看懂，因为我是蒟蒻

by Malkin_Moonlight @ 2024-08-14 20:59:42

@xuruizhe150711 其实你可以自己学学优先队列，这题用优先队列很简单

by guanzisheng2 @ 2024-08-14 21:01:53

手写堆

by Malkin_Moonlight @ 2024-08-14 21:03:39

@xuruizhe150711 哦，%%%dalao