题目描述
维护一个集合,初始时集合为空,支持如下几种操作:
I x,插入一个数 x;
PM,输出当前集合中的最小值;
DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
D k,删除第 k 个插入的数;
C k x,修改第 k 个插入的数,将其变为 x;
现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。
样例
省略了
算法1
(会TLE的算法,我们在读入每一个新的数值的时候,应该和中位数进行比较如果小于中位数就加入大根堆,大于中位数就加入小根堆,如果一直加入小根堆,那么下面就会出现大根堆堆顶比小根堆堆顶大的情况,这样为了维护对顶堆我们需要将小根堆和大根堆的堆顶互换,这个互换操作,相当于进行了两次堆的删除和插入,使复杂度增加)
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int t,n,m;
cin>>t;
while(t--)
{
priority_queue<int> q;//q为大根堆
priority_queue<int,vector<int>,greater<int>> p;//p为小根堆
cin>>n>>m;
cout<<n<<' '<<(m+1)/2<<endl;
int cnt=0;
for(int i=1;i<=m;i++)
{
cin>>n;
---------- 为什么TLE的原因,没有对加入进行判断
p.push(n);
if(q.size()&&q.top()>p.top())
{
int a=p.top(),b=q.top();
p.pop(),q.pop();
p.push(b),q.push(a);
}
----------
if(p.size()>q.size()+1)
{
q.push(p.top());
p.pop();
}
if(i&1)//奇数
printf("%d%c",p.top(),++cnt%10==0 ? '\n':' ');//每10个数换一行
}
if(cnt%10) cout<<endl;
}
return 0;
}
算法2 手写对顶堆加插入优化
(本来以为是因为用了STL的堆导致TLE,然后就尝试手写堆,结果还是TLE,最后才发现是结构上的原因,手写堆加上插入的优化应该没有更快的了)
C++ 代码
#include"cstdio"
#include"algorithm"
#include"iostream"
#include"cstring"
using namespace std;
const int N=1e5+10;
int t;
int n,m;
int h1[N],h2[N],size1,size2;
void up1(int u)
{
int t=u;
if(u/2>0&&h1[u/2]>h1[t])t=u/2;
if(u!=t)
{
swap(h1[u],h1[t]);
up1(t);
}
}
void up2(int u)
{
int t=u;
if(u/2>0&&h2[u/2]<h2[t])t=u/2;
if(u!=t)
{
swap(h2[u],h2[t]);
up2(t);
}
}
void down1(int u)
{
int t=u;
if(u*2<=size1&&h1[u*2]<h1[t])t=u*2;
if(u*2+1<=size1&&h1[u*2+1]<h1[t])t=u*2+1;
if(u!=t)
{
swap(h1[u],h1[t]);
down1(t);
}
}
void down2(int u)
{
int t=u;
if(u*2<=size2&&h2[u*2]>h2[t])t=u*2;
if(u*2+1<=size2&&h2[u*2+1]>h2[t])t=u*2+1;
if(u!=t)
{
swap(h2[u],h2[t]);
down2(t);
}
}
void add1(int h[],int x)
{
size1++;
h[size1]=x;
up1(size1);
}
void add2(int h[],int x)
{
size2++;
h[size2]=x;
up2(size2);
}
void pop1()
{
swap(h1[1],h1[size1]);
size1--;
down1(1);
}
void pop2()
{
swap(h2[1],h2[size2]);
size2--;
down2(1);
}
int main()
{
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
size1=0,size2=0;
printf("%d %d\n",n,(m+1)/2);
int cnt=0;
for(int i=1;i<=m;i++)
{
cin>>n;
if(size2==0||h2[1]>=n)
add2(h2,n);
else add1(h1,n);
if(size2>size1+1)
{
int u=h2[1];
pop2();
add1(h1,u);
}
if(size2<size1)
{
int u=h1[1];
pop1();
add2(h2,u);
}
if(i%2)
{
cout << h2[1]<<" ";
cnt++;
if(cnt%10==0) cout << endl;
}
}
if(cnt%10)cout<<endl;
}
return 0;
}