求助 小根堆
  • 板块学术版
  • 楼主Li_wenjie
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/10/10 01:00
  • 上次更新2023/10/27 08:01:57
查看原帖
求助 小根堆
457431
Li_wenjie楼主2022/10/10 01:00

题目:维护一个集合,初始时集合为空,支持如下几种操作:

I x,插入一个数 x; PM,输出当前集合中的最小值; DM,删除当前集合中的最小值(数据保证此时的最小值唯一); D k,删除第 k 个插入的数; C k x,修改第 k 个插入的数,将其变为 x; 现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。

输入格式 第一行包含整数 N。

接下来 N 行,每行包含一个操作指令,操作指令为 I x,PM,DM,D k 或 C k x 中的一种。

输出格式 对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。

每个结果占一行。

蒟蒻错误代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],n,m,_size,num;
int q[N];
void down(int u)
{
    int t=u;
    if(a[t]>=a[2*u]&&2*u<=n) t=2*u;
    if(a[t]>=a[2*u+1]&&2*u+1<=n) t=2*u+1;
    if(t!=u)
    {
        swap(a[t],a[u]);
        swap(q[t],q[u]);
        down(t);
    }
}
void up(int u)
{
    if(a[u/2]>a[u]&&u!=1)
    {
        swap(a[u/2],a[u]);
        swap(q[u/2],q[u]);
        up(a[u/2]);
    }
}
void insert(int x)
{
    a[++_size]=x;
    q[_size]=++num;
    up(x);
}
void del(int k)
{
    k=q[k];
    a[k]=a[_size--];
    down(k),up(k);
}
void del_top()
{
    del(1);
}
void change(int k,int x)
{
    k=q[k];
    a[k]=x;
    down(k),up(k);
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char c[3];
        int k,x;
        scanf("%s",c);
        //puts(c);
        if(c[0]=='I')
        {
            int x;
            cin>>x;
            insert(x);
        }
        else if(c[0]=='P')
        {
            cout<<a[1]<<endl;
        }
        else if(c[0]=='D')
        {
            if(c[1]=='M') del_top();
            else 
            {
                cin>>k;
                del(k);
            }
        }
        else 
        {
            cin>>k>>x;
            change(k,x);
        }
        
    }
}
有没有大佬告诉哪错了啊QAQ
2022/10/10 01:00
加载中...