网站开发系统需求说明书,怎么做婚恋网站,wordpress插件的选择,爱网站关键词查询对顶堆的作用主要在于动态维护第k大的数字#xff0c;考虑使用两个优先队列#xff0c;一个大9999999999根堆一个小根堆#xff0c;小根堆维护大于等于第k大的数字的数#xff0c;它的堆顶就是堆内最小#xff0c;第k大的数字#xff0c;另外一个大根堆维护小于等于k的数…对顶堆的作用主要在于动态维护第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)#includeiostream
#includequeue
#includecstring
#includealgorithm
using namespace std;int main(){int n,m;cinnm;priority_queueint a;//大根堆priority_queueint,vectorint,greaterint b;for(int i1;in;i){int x;cinx;if(b.empty()||xb.top()) b.push(x);else a.push(x);int kmax(1,i*m/100);if(b.size()k) a.push(b.top()),b.pop();if(b.size()k) b.push(a.top()),a.pop();coutb.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)#includeiostream
#includequeue
using namespace std;int main(){int n;cinn;priority_queueint a;priority_queueint,vectorint,greaterint b;for(int i1;in;i){int x;cinx;if(b.empty()||xb.top()) b.push(x);else a.push(x);if(i%2){int k(i1)/2;while(b.size()k) b.push(a.top()),a.pop();while(b.size()k) a.push(b.top()),b.pop();coutb.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)#includeiostream
#includequeue
#includevector
using namespace std;int main(){int n,m;cinnm;vectorint a(n2);vectorint b(m2);for(int i1;in;i) cina[i];for(int i1;im;i) cinb[i];b[m1]1e9;priority_queueint c;priority_queueint,vectorint,greaterint d;int cnt1,k0;for(int i1;in;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();coutc.top()endl;} }
}
4.P2085 最小函数值
原本想了想用偏暴力的方法AC了结果发现原来是数据不好
我的想法是到了一定大小x方就会作为主力
原代码如下用n1 m10000就可以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)#includeiostream
#includealgorithm
#includequeue
using namespace std;
const int N1e410;int main(){priority_queueint a;priority_queueint,vectorint,greaterint b;int n,m;cinnm;for(int i1;in;i){int x,y,z;cinxyz;for(int j1;j500;j){int kx*j*jy*jz;if(a.empty()||ka.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();vectorint c((int)a.size()1);int lena.size();for(int i1;ilen;i){c[i]a.top();a.pop();}for(int ilen;i1;--i){coutc[i] ;}coutendl;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)#includeiostream
#includealgorithm
#includequeue
using namespace std;
const int N1e410;int main(){priority_queueint a;int n,m;cinnm;for(int i1;in;i){int x,y,z;cinxyz;for(int j1;jm;j){int kx*j*jy*jz;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();vectorint c((int)a.size()1);int lena.size();for(int i1;ilen;i){c[i]a.top();a.pop();}for(int ilen;i1;--i){coutc[i] ;}coutendl;return 0;
}
