优先队列——priority queue
优先队列朴素版之简单应用
合并果子
题意：
n个果子，数目为tr[i]，进行n – 1次合并操作，每次都消耗两堆果子的重量和的体力，耗费的总体力等于每次合并所耗费的体力和，求最小值
思路1:
使用秘技STL，priority_queue来操作，但这个优先队列是从大到小的，有一个非常非常非常简便的方法来改变其顺序——加负号！！！
u1s1,STL针不戳
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
priority_queue<int>q;
int main()
{
int n, m;
cin>>n;
for(int i = 1; i <= n; ++i){
cin>>m;
q.push(-m);
}
ll ans = 0;
for(int i = 1; i < n; ++i){
int x = -q.top();
q.pop();
int y = -q.top();
q.pop();
ans += x + y;
q.push(-x - y);
}
cout<<ans<<endl;
return 0;
}
思路2:
手撕优先队列。
首先我们要知道优先队列其实是一种堆，是一棵完全二叉树，而这个二叉树又满足一个规律——任意节点都小于（或大于）其子节点
这个题我们要用到插入，弹出，取顶三个操作
插入：
对于一个新的数插进来，我们不能坏了优先队列的顺序，所以就插在最后，然后和他的父节点进行比较，看看需不需要交换，一直换下去
弹出：
对于弹出的数是队首，也就是这里面最小的（或者最大的数），所以可以直接把最后一个元素拿过来替代他，然后再和他的子节点比较，这里会出问题，因为上次是和父节点比较（众所周知，你只有一个爹，但你爹不一定只有你一个孩子，是不是很形象o(≧v≦)o），只有一个父节点，而现在和子节点比较，对于升序的优先队列，我们得取小的子节点与父节点交换
取顶：
就直接取q[1]即可
注意一些边界条件
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
inline int IntRead(){
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9'){
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
int n,q[MAX],tot, ans;
void push(int x){//塞新的数进去
q[++tot] = x;
int i = tot, j = i / 2;//i是子节点，j是父节点
while (j > 0 && q[j] > q[i]) {//没有出界且父亲节点的值大于子节点的值就交换
swap(q[i], q[j]);
i=j;j=i/2;//原来的父亲节点就成了现在的子节点，而现在的子节点是父节点除以2所得
}
}
int top(){//取顶
return q[1];
}
void pop(){//弹出队首
q[1] = q[tot];
tot--;
int i = 1, j = 2 * i;//i是父节点，j是子节点
//可能i的另一个子节点k比j小，此时就是换i和k，所以要判断一下谁更小
if (j + 1 <= tot && q[j] > q[j + 1]) {
j++;
}
while (j <= tot && q[j] < q[i]) {
swap(q[i], q[j]);
i = j;
j = i * 2;
if(j + 1 <= tot && q[j] > q[j + 1]) j++;//不能忘
}
}
int main()
{
cin>>n;
for(int i = 1; i <= n; ++i){
int x;cin>>x;
push(x);
}
for(int i = 1; i < n; ++i){
int x = top();
pop();
int y = top();
pop();
ans += x + y;
push(x + y);
}
cout<<ans<<endl;
return 0;
}
优先队列进阶版之对顶堆
对顶堆
实质上是通过维护两个堆动态处理中位数等问题
大根堆Q1：根最大，维护的是集合中较小部分的最大值（即顶堆）
小根堆Q2：根最小，维护的是集合中较大部分的最小值（同堆顶）
堆中元素都是单调的，与此同时，两个堆之间也是单调的，大根堆中任意一个元素都小于小根堆的任意一个元素
从下往上值越大
RuningMedian
题意：
给一堆数，输出前i个数中的中位数（i 是奇数）
思路：
中位数指的是一堆数中从小到大排序后（或降序）中间的数或中间两个数的平均值
所以求中位数，需要排序，但肯定不能每求一次就拿出前i个数进行排序，所以就需要另辟蹊径。
也就是需要一个数据结构，能做到快速插入数据，并快速调整，同时可以动态获取中位数
我们知道。堆是一种极其有用的数据结构（虽然我不不会(╥﹏╥))，他能在短时间内将数据维护成单调递增或递减的序列，但是一个堆并不能简单的解决本题。而两个堆做得到，中位数将序列分成两部分数量相同的序列，我们可以用两个堆将他们存起来。
因为小堆Q2是堆顶最小，大堆Q1是堆顶最大，所以对于一个新来的数x，得不能破坏他们的单调性，就拿新来的数x和两个队顶比较，如果x小于Q1的堆顶，就扔进Q1里面，反之扔进Q2里面。为了防止出现一“边倒现象”，我们就再每次插入数之后判断一下，看看有没有哪个堆的数量比另一个堆大2及以上的，如果有，多几个就扔几个堆顶进去。如果是奇数次的话，就可以存中位数，我使用的vector（数组开10000 都能爆？！我服气，只能开vector）。
这个题的输出格式也很恶心心(╥﹏╥)
每行最多十个，一行内的数与数用空格替代，但是他最后一个数得有空格是什么鬼？？？题目没说，但是我把那个空格去掉就PE了，加上就AC了！！！毫无AC体验(⌒-⌒; )
而且你得判断一下最后用不用输换行，可能你没够十个，就不会换行，就会继续输出
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
priority_queue<int>q1;//大根堆
priority_queue<int, vector<int>, greater<int>>q2;//小根堆
//不知道为什么，我写这个push函数，开始写的时候，我的Xcode报错，扔牛客又说我RE，最后我怎么看都感觉没问题，最后他又自己好了？？？我tm
void push(int x){//塞数函数
if(!q1.size() || x < q1.top())q1.push(x);
else q2.push(x);
if(q1.size() > q2.size() + 1){
q2.push(q1.top());
q1.pop();
}
if(q2.size() > q1.size() + 1){
q1.push(q2.top());
q2.pop();
}
}
vector<int>v;
int main()
{
int t, x, m , n;
cin>>t;
while (t--) {
v.clear();//多组输入，清0万岁
while (q1.size()) {
q1.pop();
}
while (q2.size()) {
q2.pop();
}
cin>>m>>n;
cout<<m<<' '<<(n + 1) / 2<<endl;
for(int i = 1; i <= n; ++i){
cin>>x;
push(x);
if(i % 2 == 1){//奇数次就存
if(q1.size() > q2.size())//找多的那个
v.push_back(q1.top());
else
v.push_back(q2.top());
}
}
for(int i = 0; i < v.size(); ++i){
cout<<v[i];
if((i + 1) % 10 != 0 && i + 1 != v.size())
cout<<' ';
else
cout<<'\n';
}
if(v.size() % 10)
cout<<'\n';
}
return 0;
}
黑匣子
题意：
两种操作，ADD（x）：把x元素放进数组里面
GET：i + 1，然后输出数组中第i小的数
思路：
动态求第k小的数，可以用对顶堆来解决
需要的是从小到大的第i个数，所以我们保持大根堆有i – 1个元素，每次只需要输出小根堆的堆顶即可
有朋友可能会问，为什么不直接保持大根堆有i个元素呢？
那是因为，可能你最后塞进大根堆的那个元素x，使得小根堆中有元素比他还小，所以就需要把第i个扔进小根堆，进行排序，这样大根堆有i-1个，我们只需要输出小根堆的堆顶即可！
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef long long ll ;
inline int IntRead(){
char ch = getchar();
int s = 0, w = 1;
while(ch < '0' || ch > '9'){
if(ch == '-') w = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
s = s * 10 + ch - '0';
ch = getchar();
}
return s * w;
}
priority_queue<int>q1;//大
priority_queue<int, vector<int>, greater<int> >q2;//小
int tr[MAX];
int main()
{
int n, m;
cin>>m>>n;
for(int i = 1; i <= m; ++i){
tr[i] = IntRead();
}
int r = 1, q;
for(int i = 1; i <= n; ++i){
cin>>q;
for(int j = r; j <= q; ++j){
q1.push(tr[j]);//扔到大根堆中去从小到大排序
//如果大根堆的数量达到i个，我就只能把栈顶的扔到小根堆中再去排序，最后会发现，大根堆中有i-1个数，所以第i大的数就是小根堆的堆顶
if(q1.size() == i){
q2.push(q1.top());
q1.pop();
}
}
cout<<q2.top()<<endl;//取小根堆的堆顶
r = q + 1;//更新r的值
q1.push(q2.top());
//因为下一次i会++，大根堆需要的数也会增加，但为了避免像样例一样出现两个相同的数字而导致不会进入循环，使得大根堆的数量得不到增加而导致的错误，就先将小根堆的堆顶扔到大根堆去
q2.pop();
}
return 0;
}