算法日记————对顶堆（4道题）

对顶堆的作用主要在于动态维护第k大的数字，考虑使用两个优先队列，一个大9999999999根堆一个小根堆，小根堆维护大于等于第k大的数字的数，它的堆顶就是堆内最小，第k大的数字，另外一个大根堆维护小于等于k的数字，堆顶是最大的，如此一来，就可以以排序的方式进行数字交换了

1.板子题 P7072 [CSP-J2020] 直播获奖

// Problem: 
//     P7072 [CSP-J2020] 直播获奖
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7072
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;int main(){int n,m;cin>>n>>m;priority_queue<int> a;//大根堆priority_queue<int,vector<int>,greater<int>> b;for(int i=1;i<=n;++i){int x;cin>>x;if(b.empty()||x>=b.top()) b.push(x);else a.push(x);int k=max(1,i*m/100);if(b.size()>k) a.push(b.top()),b.pop();if(b.size()<k) b.push(a.top()),a.pop();cout<<b.top()<<' ';}return 0;
}

2.中位数

不知道为啥开绿题，可能是没标签我就想不到用对顶堆

代码如下

// Problem: 
//     P1168 中位数
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1168
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
using namespace std;int main(){int n;cin>>n;priority_queue<int> a;priority_queue<int,vector<int>,greater<int>> b;for(int i=1;i<=n;++i){int x;cin>>x;if(b.empty()||x>b.top()) b.push(x);else a.push(x);if(i%2){int k=(i+1)/2;while(b.size()<k) b.push(a.top()),a.pop();while(b.size()>k) a.push(b.top()),b.pop();cout<<b.top()<<endl;}}return 0;
}

3.P1801 黑匣子

这道题反其行之，维护的是第k小，实际上是一样的，我们稍微想想就能发现，第k小的数字不就是大根堆的堆顶吗，稍微改一下代码就行。

这道题让我找到了对顶堆的局限性：动态查第k个数字，变化不能很大，否则就会TLE（限定）

// Problem: 
//     P1801 黑匣子
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1801
// Memory Limit: 500 MB
// Time Limit: 500 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
#include<vector>
using namespace std;int main(){int n,m;cin>>n>>m;vector<int> a(n+2);vector<int> b(m+2);for(int i=1;i<=n;++i) cin>>a[i];for(int i=1;i<=m;++i) cin>>b[i];b[m+1]=1e9;priority_queue<int> c;priority_queue<int,vector<int>,greater<int>> d;int cnt=1,k=0;for(int i=1;i<=n;++i){if(c.empty()||a[i]<c.top()) c.push(a[i]);else d.push(a[i]);while(b[cnt]<=i){k++;cnt++;while(c.size()>k) d.push(c.top()),c.pop();while(c.size()<k) c.push(d.top()),d.pop();cout<<c.top()<<endl;} }
}

4.P2085 最小函数值

原本想了想，用偏暴力的方法AC了，结果发现原来是数据不好（

我的想法是到了一定大小，x方就会作为主力，

原代码如下（用n=1 m=10000就可以hack掉）

// Problem: 
//     P2085 最小函数值
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2085
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+10;int main(){priority_queue<int> a;priority_queue<int,vector<int>,greater<int>> b;int n,m;cin>>n>>m;for(int i=1;i<=n;++i){int x,y,z;cin>>x>>y>>z;for(int j=1;j<=500;++j){int k=x*j*j+y*j+z;if(a.empty()||k<=a.top()) a.push(k);else b.push(k);}}while(a.size()>m) b.push(a.top()),a.pop();while(a.size()<m) a.push(b.top()),b.pop();vector<int> c((int)a.size()+1);int len=a.size();for(int i=1;i<=len;++i){c[i]=a.top();a.pop();}for(int i=len;i>=1;--i){cout<<c[i]<<' ';}cout<<endl;return 0;	
}

这里有一种优化的方法，也就是加入了一个break，在一定次数后操作次数就会变得很少就会导致break掉。这里其实无需维护那个小根堆，直接维护大根堆即可，因为小根堆的作用是处理那个变化的m，这里的m是不变的

// Problem: 
//     P2085 最小函数值
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2085
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e4+10;int main(){priority_queue<int> a;int n,m;cin>>n>>m;for(int i=1;i<=n;++i){int x,y,z;cin>>x>>y>>z;for(int j=1;j<=m;++j){int k=x*j*j+y*j+z;if(a.size()<m) a.push(k);else{if(a.top()>k) a.push(k),a.pop();else break;}}}//while(a.size()>m) b.push(a.top()),a.pop();//while(a.size()<m) a.push(b.top()),b.pop();vector<int> c((int)a.size()+1);int len=a.size();for(int i=1;i<=len;++i){c[i]=a.top();a.pop();}for(int i=len;i>=1;--i){cout<<c[i]<<' ';}cout<<endl;return 0;	
}