优先队列¶

实际上是一个STL。可以实现堆的功能。默认是大根堆（c++如此，其他语言可能有所不同）

例题 #1 指针堆最小函数值¶

有 \(n\) 个函数，分别为 \(F_1,F_2,\dots,F_n\)。定义 \(F_i(x)=A_ix^2+B_ix+C_i(x\in\mathbb N*)\)。给定这些 \(A_i\)、\(B_i\) 和 \(C_i\)，请求出所有函数的所有函数值中最小的 \(m\) 个（如有重复的要输出多个）。

输入格式

第一行输入两个正整数 \(n\) 和 \(m\)。

以下 \(n\) 行每行三个**正整数**，其中第 \(i\) 行的三个数分别为 \(A_i\)、\(B_i\) 和 \(C_i\)。

输出格式

输出将这 \(n\) 个函数所有可以生成的函数值排序后的前 \(m\) 个元素。这 \(m\) 个数应该输出到一行，用空格隔开。

很担心的将指针丢入优先队列的题目。考虑每个函数就是一个无限长的队列，队列里的元素是单调递增的。我们使用优先队列维护所有队列的头元素，每次取出最小的，弹出，然后将后面应该元素推入。

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int

#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}

#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

int a[N],b[N],c[N];
int pre[N];

int getVal(int x){
    return a[x]*pre[x]*pre[x]+b[x]*pre[x]+c[x];
}


priority_queue<pii> pq;


void solve(){
    int n=rd;
    itn m=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
        b[i]=rd;
        c[i]=rd;
        pre[i]=max(1ll,-2*a[i]/b[i]);
        pq.push(mp(-getVal(i),i));
    }


    while(m--){
        int x=pq.top().ps;
        cout<<getVal(x)<<' ';
        pq.pop();
        pre[x]++;
        pq.push(mp(-getVal(x),x));
    }
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

多个队列替代优先队列/set¶

特殊场合下多个队列替代优先队列，降低时间复杂度。

例题 #1 [NOIP2004 提高组] 合并果子加强版¶

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 \((n - 1)\) 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 \(1\)，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 \(3\) 堆果子，数目依次为 \(1,~2,~9\)。可以先将 \(1\)、\(2\) 堆合并，新堆数目为 \(3\)，耗费体力为 \(3\)。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 \(12\)，耗费体力为 \(12\)。所以多多总共耗费体力为 \(3+12=15\)。可以证明 \(15\) 为最小的体力耗费值。

输入格式

输入的第一行是一个整数 \(n\)，代表果子的堆数。输入的第二行有 \(n\) 个用空格隔开的整数，第 \(i\) 个整数代表第 \(i\) 堆果子的个数 \(a_i\)。

输出格式

输出一行一个整数，表示最小耗费的体力值。

Subtask 4（40 points）：\(1 \leq n \leq 10^7\)。

对于全部的测试点，保证 \(1 \leq a_i \leq 10^5\)。

原来需要优先队列的做法是带log的，在这里会被卡掉。我们考虑原做法：每次取出最小的两堆，合并。那么我们发现我们合并后的堆的大小是单调递增的，于是我们就可以维护序列p,q，一开始桶排a后加入p，每次比较p,q的top，和p的前两个top，取最小值，弹出后加入q的队尾。

/*
Code by Ntsc_Hodaka
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int,int>

///----///
#define rd read()
inline int read() {
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
inline void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

///----///
const int N = 1e7 + 5;
const int M = 1e5 + 5;
const int INF = 1e9 + 5;
const int MOD = 1e9+7;
const double eps=1e-7;
int n,a[N],ans,cnt[N];

queue<int> q1,q2;

int qfront(){
    int res;
    if(q2.empty()||(q1.size()&&q1.front()<q2.front())){res=q1.front();q1.pop();}
    else {res=q2.front();q2.pop();}
    return res;

}
signed main(){
    n=rd;
    for(int i=1;i<=n;i++){
        a[i]=rd;
        cnt[a[i]]++;    
    }
    for(int i=1;i<=M;i++){
        while(cnt[i]--){//桶排
            q1.push(i);
            // cout<<i<<' ';
        }
    }

    for(int i=1;i<n;i++){
        int a=qfront(),b=qfront();
        ans+=a+b;
        q2.push(a+b);

    }
    cout<<ans;
    return 0;
}

练习 #1 [NOIP2016 提高组] 蚯蚓¶

/*
CB Ntsc
*/

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair

#define rd read()
inline int read() {
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
inline void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}



const int N = 1e7 + 5;
const int M = 40;
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;

int n,m,q,u,v,t,top,sum;
priority_queue<int> ans;
int cn1[N],cn2[N],a[N],h1=1,h2=1,h=1,t1,t2;

bool cmp(int x,int y){
    return x>y;
}
signed main(){
    n=rd,m=rd,q=rd,u=rd,v=rd,t=rd;
    double p=1.00*u/v;
    for(int i=1;i<=n;i++){
        a[i]=rd;
    }

    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=m;i++){
        if(h>n){
            if(cn1[h1]>cn2[h2])top=cn1[h1++];
            else top=cn2[h2++];
        }
        else if(a[h]>=cn1[h1]&&a[h]>=cn2[h2])top=a[h++];
        else if(cn1[h1]>=cn2[h2]&&a[h]<=cn1[h1])top=cn1[h1++];
        else top=cn2[h2++];

        top+=sum;

        int a1=floor(1.00*p*top),a2=top-a1;

        sum+=q;
        a1-=sum;a2-=sum;

        cn1[++t1]=a1,cn2[++t2]=a2;

        if(!(i%t))cout<<top<<' ';
    }

    cout<<endl;
    for(int i=h;i<=n;i++)ans.push(a[i]);
    for(int i=h1;i<=t1;i++)ans.push(cn1[i]);
    for(int i=h2;i<=t2;i++)ans.push(cn2[i]);
    int i=1;
    while(ans.size()){
        if(!(i%t))cout<<ans.top()+sum<<' ';
        ans.pop();
        i++;
    }
    return 0;

}
/*
1
2 5 1 
0 0 1 
0 0 4 

*/

练习 #2 [CSP-S2020] 贪吃蛇¶

首先肯定是优化模拟，因为每一轮要么蛇数量-1，要么exit。

考虑限制：每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇

怎么样判断一个时刻也不应该吃呢？

设当前蛇的集合的最大值为mx，最小值为mn，那么吃了之后变为mx-mn。如果此时mx-mn不是最小的，那么一定选择吃。

证明：设集合从小到大为\(a,b,\dots,c,d\)，那么模拟一次，变为了\(b,\dots,d-a,c\)，接下来是\(\dots,c-b,d-a\)。我们发现一直有蛇在d前面当垫背。为什么c-b<d-a呢？基本的排序不等式！

如果此时mx-mn是最小的，下一个最大值也不一定会吃它。此时我们就考虑下一个最大值会不会吃它，如果不会那么久mx就可以吃mn，否则游戏结束。

假设当前集合的最大值，次大值，……分别为a,b,c,\dots。我们考虑，如果a吃，那么意味着b不吃。也就是说这种情况最多只能再进行一次吃的操作，游戏必然结束。

那么到底是吃不吃？

如果a吃，那么b必然不吃。b不吃是因为如果b吃，那么c就会吃b，此时b一定不吃。那么c吃意味着d不吃……

我们发现吃和不吃是轮换的。知道最后，只有两条蛇时，一定吃。我们看作一个递归，那么如果集合大小为奇数，那么必然不能吃，否则就吃。

到此，思路就完结了。因为我们要维护max和min，所以我们考虑set。

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int

#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}

#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

int a[N];
int n;
set<pii> st;

void solve(){
    // cdbg(st.size());
    for(int i=1;i<=n;i++){
        st.insert(mp(a[i],i));
    }

    int ans=0;
    int f=0;//标记阶段2

    while(1){
        // cdbg("OK");
        if(st.size()==2){
            st.erase(st.begin());
            if(f){
                if(1&(f-st.size()))ans=f+1;
                else ans=f;
            }else{
                ans=1;
            }
            break;

        }

        auto mx=st.end();
        mx--;
        int vmx=(*mx).pf;
        int mxid=(*mx).ps;
        st.erase(mx);
        auto mn=st.begin();
        int vmn=(*mn).pf;
        st.erase(mn);
        auto mn2=st.begin();
        // st.erase(mn2);


        int mx2=vmx-vmn;
        st.insert(mp(mx2,mxid));//注意相等时判id
        if(mxid!=(*st.begin()).ps){
            if(f){
                if(1&(f-st.size()))ans=f+1;
                else ans=f;
                break;
            }

          // #2，意思是把上面的insert放到这里。
        }else{
            // #1
            if(!f)f=st.size();//进入阶段2
        }
    }
    cout<<ans<<endl;
    st.clear();
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);

    int T=rd;
    int TT=0;
    while(T--){
        if(!TT){
             n=rd;
            for(int i=1;i<=n;i++){
                a[i]=rd;
            }
        }else{
            int K=rd;
            for(int i=1;i<=K;i++){
                // cdbg("cg");
                int x=rd,y=rd;
                a[x]=y;
            }
        }
        solve();
        TT++;
    }
    return 0;
}

但是发现70pts高分，过不去（\(\sum n=Tn=O(10^7)\)）那么我们就拿出我们的队列替代。

怎么替代？

我们发现我们的操作只有：删除最大值，删除最小值，插入最小值（#1），插入任意值（#2）。

前两个用一个队列即可。插入值？我们考虑性质：#2 插入的值是递减的。那么就很好写了。我们用两个队列维护，打包一下更清楚。

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int

#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}

#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 1e6 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

int a[N];
int n;



namespace douque{
    //两个单调递增的队列
    list<pii> q,q2;
    pii queryMin(bool del=0){
        pii res;
        if(!q2.size()){
            res=q.front();
            if(del)q.pop_front();
        }
        else if(!q.size()){
            res=q2.front();
            if(del)q2.pop_front();
        }
        else if(q.front().pf<q2.front().pf||(q.front().pf==q2.front().pf&&q.front().ps<q2.front().ps)){
            res=q.front();
            if(del)q.pop_front();
        }else{
            res=q2.front();
            if(del)q2.pop_front();
        }
        return res;
    }

    pii queryMax(bool del=0){
        pii res;
        if(!q2.size()){
            res=q.back();
            if(del)q.pop_back();
        }
        else if(!q.size()){
            res=q2.back();
            if(del)q2.pop_back();
        }
        else if(q.back().pf>q2.back().pf||(q.back().pf==q2.back().pf&&q.back().ps>q2.back().ps)){
            res=q.back();
            if(del)q.pop_back();
        }else{
            res=q2.back();
            if(del)q2.pop_back();
        }
        return res;

    }

    int getsz(){
        return q.size()+q2.size();
    }
}using namespace douque;

void solve(){
    for(int i=1;i<=n;i++){
        q.push_back(mp(a[i],i));
    }



    int ans=0;
    int f=0;//标记阶段2

    while(1){
        if(getsz()==2){
            queryMin(1);
            if(f){
                if(1&(f-1))ans=f+1;
                else ans=f;
            }else{
                ans=1;
            }
            break;

        }

        auto mx=queryMax(1);
        int vmx=(mx).pf;
        int mxid=(mx).ps;
        auto mn=queryMin(1);
        int vmn=(mn).pf;
        // auto mn2=queryMin();

        int mx2=vmx-vmn;
        if(!(mx2<queryMin().pf||(mx2==queryMin().pf&&mxid<queryMin().ps)) ){
            if(f){
                if(1&(f-getsz()-1))ans=f+1;
                else ans=f;
                break;
            }
            q2.push_front(mp(mx2,mxid));
        }else{
            q.push_front(mp(mx2,mxid));
            if(!f)f=getsz();//进入阶段2
        }
    }
    cout<<ans<<endl;
    while(q.size())q.pop_back();
    while(q2.size())q2.pop_back();
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);

    int T=rd;
    int TT=0;
    while(T--){
        if(!TT){
             n=rd;
            for(int i=1;i<=n;i++){
                a[i]=rd;
            }
        }else{
            int K=rd;
            for(int i=1;i<=K;i++){
                // cdbg("cg");
                int x=rd,y=rd;
                a[x]=y;
            }
        }
        solve();
        TT++;
    }
    return 0;
}

优先队列¶

优先队列¶

例题 #1 指针堆 最小函数值¶

多个队列替代优先队列/set¶

例题 #1 [NOIP2004 提高组] 合并果子 加强版¶

练习 #1 [NOIP2016 提高组] 蚯蚓¶

练习 #2 [CSP-S2020] 贪吃蛇¶

例题 #1 指针堆最小函数值¶

例题 #1 [NOIP2004 提高组] 合并果子加强版¶