优先队列、map 与 set · SpringWait Blog

栈和队列已经学过，先复习它们规定的处理顺序。再考虑两类新要求：候选不断增删时，每次取出当前最值；使用姓名、长度等关键字查找记录。容器的选择取决于这些操作，而不是题目中出现了哪些名词。

一、栈和队列：按加入顺序处理

栈遵循后进先出，只能从栈顶取出最近加入且尚未删除的元素。队列遵循先进先出，从队首取出最早加入且尚未删除的元素。

把 $4,1,3$ 依次加入，再取出一个元素：

结构	加入后的顺序	第一次取出	剩下的元素
栈	栈底到栈顶为 $4,1,3$	$3$	栈底到栈顶为 $4,1$
队列	队首到队尾为 $4,1,3$	$4$	队首到队尾为 $1,3$

如果此时再加入 $5$ ，栈下一次取出 $5$ ，队列下一次取出 $1$ 。两者都只关心加入顺序，不会主动比较数值大小。

操作	栈	队列
声明	$\texttt{stack<int> s}$	$\texttt{queue<int> q}$
加入 $x$	$s.push(x)$	$q.push(x)$
读取待取出的元素	$s.top()$	$q.front()$
删除待取出的元素	$s.pop()$	$q.pop()$
判断是否为空	$s.empty()$	$q.empty()$

这些基本操作的时间复杂度都是 $O(1)$ 。读取和删除前必须保证非空； $pop()$ 只删除元素，不返回被删除的值，需要时应先读取再删除。

stack<int> s;
s.push(4);
s.push(1);
s.push(3);
if(!s.empty()){
    int x=s.top();
    s.pop();
    cout<<x<<'\n';
}

queue<int> q;
q.push(4);
q.push(1);
q.push(3);
if(!q.empty()){
    int x=q.front();
    q.pop();
    cout<<x<<'\n';
}

括号匹配使用栈，是因为右括号要先匹配最近一个尚未匹配的左括号。按到达顺序处理等待任务使用队列，是因为最早到达的任务先处理。若改为“优先处理当前最紧急的任务”，加入顺序就不再决定取出顺序。

二、优先队列：动态取出当前最值

例题：合并果子

P1090 合并果子要求把 $n$ 堆果子合成一堆，每次任选两堆合并，代价为它们的重量之和，新堆仍可参加后续合并。求总代价的最小值。

例如有四堆果子，重量分别为 $1,2,3,4$ 。可以先把 $1,2$ 合成 $3$ ，再把原来的 $3,4$ 合成 $7$ ，最后把 $3,7$ 合成 $10$ 。这三次合并的总代价为

3+7+10=20.

也可以在第一次得到新堆 $3$ 后，把它与原来的 $3$ 合成 $6$ ，最后把 $6,4$ 合成 $10$ 。这样总代价为

3+6+10=19.

最后一堆的重量都是 $10$ ，合并顺序却会改变中间几次的花费。因此，答案是每次合并代价的总和，不能只把最初的重量加起来。

每次合并当前最轻的两堆

在第二种方案中，最初重量为 $1$ 的果子参加了三次合并：它的重量包含在本轮代价 $3$ 、下一轮代价 $6$ 和最后一轮代价 $10$ 中。重量为 $4$ 的果子只参加了最后一次合并，重量只计入一次。

一堆果子参加几次合并，它的重量就会被计入总代价几次。让较轻的果子多参加几次、较重的果子少参加几次，有利于减小总代价。对于这道允许任选两堆的题，可以每次合并当前最轻的两堆，得到最小总代价。完整的理由见后面的“贪心依据”小节。

按照这条规则，每一轮做三件事：

从现有的果堆中找到最轻的两堆，设重量为 $x,y$ 。
将它们合成重量为 $x+y$ 的新堆，把 $x+y$ 加入累计代价。
删除被合并的两堆，加入新堆，再继续选择。

只有一堆时就结束。继续手算重量为 $1,2,3,4$ 的情况：

次数	合并前的重量	取出的两堆	加回的新重量	累计代价
$1$	$1,2,3,4$	$1,2$	$3$	$3$
$2$	$3,3,4$	$3,3$	$6$	$9$
$3$	$4,6$	$4,6$	$10$	$19$

表中的重量按从小到大列出，便于观察每次选的是哪两堆。第一次合并以后，现有的三堆是 $3,3,4$ ，下一轮就应选择两个 $3$ 。新堆和原来的堆一样，都要参加后续选择。

直接扫描数组，找出最轻的两堆

可以先用数组保存现有的果堆重量。每轮扫描数组，找出重量最小的一堆；再扫描一次，跳过刚才选中的那一堆，找出第二小的一堆。随后按前面的步骤合并、累计代价，并更新数组中的果堆。

即使两堆重量相同，它们也是两堆不同的果子。例如 $3,3,4$ 中的两个 $3$ 都必须保留，才能在下一轮合并。

若这一轮有 $m$ 堆，找出最轻的两堆需要 $O(m)$ 时间。每轮合并后少一堆，因此要依次处理 $n,n-1,\ldots,2$ 堆，总时间为 $O(n^2)$ 。

重复工作发生在查找时：每轮只有两堆被移除、一堆被加入，其余果堆的重量都没有变化，但下一轮又把它们全部扫描了一遍。需要一个能够在加入、删除果堆之后，快速给出当前最小重量的容器。

用默认大根堆取出最小重量

C++ 的优先队列可以在元素不断加入、删除时，按大小决定下一次取出谁。下面是默认的大根堆写法，堆顶始终是当前存入的最大值：

priority_queue<int> q;

合并果子需要取最小重量，可以在入堆时把重量取相反数。例如重量为 $1,2,3,4$ ，就存入 $-1,-2,-3,-4$ 。其中最大的是 $-1$ ，对应的正好是最小重量 $1$ 。原来的数越小，取相反数后就越大，因此仍用默认大根堆即可。

每次加入重量 $x$ 时，执行 $q.push(-x)$ 。读取时， $q.top()$ 是重量的相反数，必须用 $-q.top()$ 还原实际重量。随后调用 $q.pop()$ 删除这一项，再读取并还原下一项，就能得到第二轻的一堆。将两堆合并后，执行 $q.push(-(x+y))$ ，让新堆也按相同规则参加后续选择。

在刚才的例子中，先取出 $-1,-2$ ，还原成重量 $1,2$ ，合并后存回 $-3$ 。此时堆中有两个 $-3$ 和一个 $-4$ ，下一轮取出的就是两堆重量均为 $3$ 的果子。

操作	在合并果子中的作用	堆中有 $m$ 个元素时的复杂度
$q.push(-x)$	存入重量的相反数，加入重量为 $x$ 的果堆	$O(\log(m+1))$
$-q.top()$	还原并读取最轻一堆的重量	$O(1)$
$q.pop()$	删除最轻的一堆	$O(\log(m+1))$
$q.empty()$ 、 $q.size()$	查询是否为空、还剩多少堆	$O(1)$

优先队列允许保存重复值。两个重量均为 $3$ 的果堆对应两个 $-3$ ，可以同时放进去，弹出一次只删除其中一堆。 $pop()$ 不返回重量，所以要先读取并还原，再删除；读取和删除都要求堆非空。

大根堆保证堆顶是存入数值中的最大值，其余元素不一定整体有序。这里通过取相反数，让堆顶对应最小重量；前面表格中按大小排列的重量，只是手算时列出的顺序。

若题目要求每次取最大值，直接存入原值、读取堆顶即可。本讲义统一使用默认大根堆，根据取出顺序决定是否取相反数。

优先队列没有直接按下标访问或删除任意指定元素的接口，需要根据题目实际要求选择。

合并果子参考程序

输入第一行是 $n$ ，第二行是 $n$ 个重量。原题保证 $1\le n\le10^4$ 、 $1\le a_i\le2\times10^4$ ，并额外保证最优总代价小于 $2^{31}$ 。重量均为正，发生合并时的中间重量和累计代价都不会超过最终总代价，因此下面程序使用 $\texttt{int}$ 。

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q;

int main(){
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        int x;
        cin>>x;
        q.push(-x);
    }
    while(q.size()>1){
        int x=-q.top();
        q.pop();
        int y=-q.top();
        q.pop();
        ans+=x+y;
        // 新堆仍要参加合并，入堆时也存相反数。
        q.push(-(x+y));
    }
    cout<<ans<<'\n';
    return 0;
}

程序先把全部重量的相反数放入堆。只要还剩至少两堆，就取出并还原最小的两个重量，累加合并代价，再把新重量的相反数放回。这样，堆中始终保存当前各堆重量的相反数，而 $x,y$ 和累计代价使用实际重量计算。

每轮取出两项、加入一项，果堆数量减少 $1$ ，所以共合并 $n-1$ 次。每次合并只需要两次删除和一次插入，不再扫描全部重量。加上最初的 $n$ 次插入，总时间为 $O(n\log(n+1))$ ，空间为 $O(n)$ 。 $n=1$ 时已经只有一堆，循环不执行，答案为 $0$ 。

整数类型仍需随题目范围判断。例如改成三堆重量均为 $10^9$ ，最后一堆重量为 $3\times10^9$ ，总代价为 $5\times10^9$ 。此时堆中元素、取出的 $x,y$ 和累计代价都应使用 $\texttt{long long}$ ，不能只把最终答案改成较宽的类型。

贪心依据（补充）：较小的重量安排更多次合并

一次完整的合并方案可以画成树：最初的每堆果子是叶子，每次合并产生一个父结点，两个被合并的对象是它的孩子。某堆果子从叶子到根经过多少条边，就参加了多少次合并。若重量为 $w_i$ ，边数为 $d_i$ ，它对总代价的贡献就是 $w_i d_i$ 。

若 $a\le b$ ，两个叶子位置的深度为 $p\le q$ ，把较小的重量放在更深的位置，代价变化为

(aq+bp)-(ap+bq)=(a-b)(q-p)\le0.

因此，较小的重量换到更深的位置不会增加代价。在合并树中，最深叶子的兄弟也是叶子，而且同样深；否则兄弟还有孩子，就会出现更深的叶子。于是，可以把最小的两个重量交换到这对位置，得到一个仍然最优的方案，让它们直接合并。

把这两个叶子缩成重量为 $a+b$ 的一堆，剩下的任务仍是同样的合并问题，总代价只额外增加 $a+b$ 。缩小后的任务也必须使用最优方案，否则就能改进原方案。因此可以先合并最小两项，再重复这个规则。树的存储和遍历不影响本题实现，相关内容见第十一章的哈夫曼树部分。

这个结论依赖于“任选两堆”。如果规定只能合并相邻两堆，例如 $1,100,1$ 中的两个 $1$ 就不能直接合并，需要重新分析。

补充：相同优先级按编号处理

有些任务除了要求优先级较高的先处理，还规定优先级相同时编号较小的先处理。此时不能只保存优先级，否则取出时无法知道对应的任务编号。

把一个任务保存为 $\texttt{pair<int,int>}$ ，即包含两个整数的记录。C++ 比较 pair 时先比较第一项，第一项相同才比较第二项。放进默认大根堆后，第一项较大的先取出；第一项相同时，第二项较大的先取出。

设任务优先级为 $p$ ，编号为 $id$ 。优先级越大越先处理，因此第一项直接保存 $p$ ；编号越小越先处理，因此第二项保存 $-id$ 。这样把任务保存为 $(p,-id)$ ，就能满足题目的两个条件。输出时，再将第二项取相反数，还原任务编号。

例如依次加入“优先级 $4$ 、编号 $8$ ”“优先级 $7$ 、编号 $6$ ”“优先级 $7$ 、编号 $2$ ”，堆中保存 $(4,-8),(7,-6),(7,-2)$ 。第一项最大的两个任务优先级都是 $7$ ，再比较第二项，因为 $-2>-6$ ，第一次取出编号 $2$ 。若再加入“优先级 $8$ 、编号 $1$ ”，下一次取出编号 $1$ ，随后才是编号 $6$ 。新任务仍需与全部等待任务比较。

以下是独立的课堂任务：输入操作数 $m$ ；操作 1 p id 加入任务，操作 2 取出并输出待处理任务的编号，空时输出 EMPTY。保证 $1\le m\le10^5$ 、 $1\le p,id\le10^9$ ，每个任务编号只加入一次。

#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>> q;

int main(){
    int m;
    cin>>m;
    for(int i=1;i<=m;++i){
        int op;
        cin>>op;
        if(op==1){
            int p,id;
            cin>>p>>id;
            // 同优先级时，负编号较大的任务先取出。
            q.push({p,-id});
        }else if(q.empty()){
            cout<<"EMPTY\n";
        }else{
            cout<<-q.top().second<<'\n';
            q.pop();
        }
    }
    return 0;
}

在给定范围内， $-id$ 不会越过 $\texttt{int}$ 的下界。优先队列保存的是所有尚未处理的任务；pair 的比较规则与题目的两个优先条件一致。总时间为 $O(m\log(m+1))$ ，空间为 $O(m)$ 。若任务要求修改已经入堆的优先级，这段程序就不能直接使用。

三、map 与 set：按姓名统计并保留首次出现顺序

例题：排除名单中的姓名不参与统计

给出一份排除名单，再按到达顺序给出若干姓名。名单中的人不参与统计；对于其他人，统计每个姓名出现了几次，最后按第一次出现的先后顺序输出姓名和次数。

例如排除名单只有 Li，到达记录为：

Zhou Li Wu Zhou Chen Wu Li

Li 的两次出现都不计入。Zhou 出现了两次，Wu 出现了两次，Chen 出现了一次；这三个姓名第一次出现的顺序是 Zhou、Wu、Chen，所以输出为：

3
Zhou 2
Wu 2
Chen 1

第一行的 $3$ 表示有三个不同的姓名参与统计，不是总共读到了三个姓名。

读到一个姓名时，先排除，再统计

按输入顺序处理每个姓名 $s$ ：

在排除名单中查找 $s$ 。如果找到，就跳过这次记录。
在已经统计过的姓名中查找 $s$ 。如果找到，就把它的次数加一。
如果此前没有统计过 $s$ ，就新建一条次数为 $1$ 的记录，并把这个姓名记在首次出现顺序的末尾。

第一次读到 Zhou 时，新建记录；第二次读到 Zhou 时，只增加次数，不再把它加到顺序表中。继续处理前面的例子：

读到的姓名	是否排除	次数变化	首次出现顺序
Zhou	否	新建 Zhou，次数为 $1$	Zhou
Li	是	跳过，不统计	Zhou
Wu	否	新建 Wu，次数为 $1$	Zhou、Wu
Zhou	否	Zhou 的次数变为 $2$	Zhou、Wu
Chen	否	新建 Chen，次数为 $1$	Zhou、Wu、Chen
Wu	否	Wu 的次数变为 $2$	Zhou、Wu、Chen
Li	是	跳过，不统计	Zhou、Wu、Chen

这样，每个参与统计的姓名只在顺序表中出现一次。全部输入处理完后，按这张表依次输出姓名和它的次数即可。

直接用数组保存姓名和次数

可以用一个字符串数组保存排除名单，再用两个数组分别保存已经统计的姓名和对应次数。每读到一个姓名，先扫描排除名单，确认它不需要被跳过；再扫描已经统计的姓名，找到后更新次数，找不到时就在末尾添加一条记录。

这个做法能够得到正确答案。新姓名总是加在末尾，因此记录本身的排列顺序也就是首次出现顺序。

问题仍在查找。设有 $k$ 个排除姓名、 $n$ 条到达记录，每次都扫描排除名单，需要至多 $O(nk)$ 次姓名比较；当到达的姓名各不相同时，查找已有记录还需要 $O(n^2)$ 次比较。

本题 $n,k$ 都可以达到 $10^5$ ，逐个比较姓名的次数过多。统计的步骤不用改变，需要加快的是两种查找：这个姓名是否被排除，以及这个姓名已经出现了几次。

用 set 查找排除名单

set 可以保存一组互不相同的姓名，并支持快速查找。这里把排除名单放进 $ban$ ：

set<string> ban;

读到一个排除姓名 $s$ 时，用 $ban.insert(s)$ 加入名单。即使名单中重复给出同一个姓名，set 中也只保留一份，不影响是否排除的判断。

$ban.find(s)$ 在名单中查找 $s$ 。找到时返回这个姓名的位置；找不到时返回 $ban.end()$ 。 $end()$ 表示越过最后一个元素的位置，不是一个实际姓名，可以用它判断查找失败。

因此，处理到达记录时可以这样跳过被排除的人：

if(ban.find(s)!=ban.end())continue;

这里只关心姓名在不在名单中，所以 set 不需要给姓名再配一个次数。

用 map 记录每个姓名的次数

没有被排除的姓名需要对应一个次数。map 可以保存这样的对应关系：给出姓名，就能找到这个姓名的次数。

map<string,int> cnt;

这里字符串姓名是查找用的关键字，整数是对应的次数。例如， $\texttt{cnt["Zhou"]}$ 访问 Zhou 的次数， $\texttt{cnt["Wu"]}$ 访问 Wu 的次数。

执行 $cnt[s]$ 时，如果 $s$ 已经存在，就访问已有次数；如果不存在，map 会先为它建立一条次数为 $0$ 的记录。因此，执行下面这句就能同时处理首次出现和再次出现：

++cnt[s];

第一次出现时，次数从 $0$ 变成 $1$ ；以后每出现一次，就在原来的次数上加一。姓名不需要先转换成整数编号，也不需要扫描所有已记录的姓名。

另外保存首次出现的顺序

map 能根据姓名找到次数，但默认按姓名的字典序排列。前面三个姓名在 map 中的顺序是 Chen、Wu、Zhou，题目要求的却是 Zhou、Wu、Chen。因此，改用 map 计数后，还需要另外保存首次出现顺序。

用 $a$ 保存这张顺序表：

vector<string> a;

vector 可以看作长度能够增长的数组， $a.push\_back(s)$ 把姓名 $s$ 加在末尾。只有一个姓名第一次参与统计时，才把它加入 $a$ 。

判断第一次出现时，用 $cnt.find(s)$ 查找。它和 set 的 $find$ 一样，找不到时返回 $cnt.end()$ ，而且查询本身不会新建记录。于是，处理一个未被排除的姓名只需：

if(cnt.find(s)==cnt.end())a.push_back(s);
++cnt[s];

这两句的顺序有原因。第一次读到 Zhou 时，先查找，发现它还没有记录，就把 Zhou 加入顺序表；再增加次数，建立次数为 $1$ 的记录。如果先执行 $cnt[s]$ ，记录已经被建立，后面的查找就会认为它此前出现过，漏掉这次加入顺序表的机会。

最终输出时，按 $a$ 中的顺序取出姓名，再用 $cnt[s]$ 读取对应次数。到这里，三个容器各自负责一件事： $ban$ 判断是否排除， $cnt$ 保存次数， $a$ 保存输出顺序。

姓名统计参考程序

本题沿用第九章的姓名统计任务。输入第一行是排除姓名数 $k$ 和到达记录数 $n$ ，随后是 $k$ 个排除姓名和 $n$ 个到达姓名，空白分隔。保证 $0\le k\le10^5$ 、 $1\le n\le10^5$ ，姓名为长度 $1$ 至 $20$ 的英文字母串，区分大小写。输出不同的参与统计姓名数，再按首次出现顺序逐行输出姓名与次数。

前面的例子对应输入：

1 7
Li
Zhou Li Wu Zhou Chen Wu Li

#include <bits/stdc++.h>
using namespace std;
set<string> ban;
map<string,int> cnt;
vector<string> a;

int main(){
    int k,n;
    cin>>k>>n;
    for(int i=1;i<=k;++i){
        string s;
        cin>>s;
        ban.insert(s);
    }
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        if(ban.find(s)!=ban.end())continue;
        // 首次出现的判断必须在下标访问建立记录之前。
        if(cnt.find(s)==cnt.end())a.push_back(s);
        ++cnt[s];
    }
    cout<<a.size()<<'\n';
    for(string s:a)cout<<s<<' '<<cnt[s]<<'\n';
    return 0;
}

每条未被排除的记录恰好让对应次数增加一次，所以 $cnt$ 中的次数就是该姓名实际参与统计的次数。每个姓名只在第一次参与统计时加入 $a$ ，所以 $a$ 没有重复，且排列顺序符合题目要求。

如果所有姓名都在排除名单中， $cnt$ 和 $a$ 都为空，程序只输出一行 $0$ 。本题任意一个姓名的次数都不超过 $n$ ，使用 $\texttt{int}$ 足够。

每读入一个姓名，只执行常数次 set 或 map 的插入、查找。设姓名最大长度为 $L$ ，每次操作需要 $O(\log(n+k+1))$ 次姓名比较，每次比较最多检查 $O(L)$ 个字符。因此，总时间为 $O((n+k)L\log(n+k+1))$ ，空间为 $O((n+k)L)$ 。

补充：只查询时，不要意外新建记录

如果只是想知道 Wang 是否出现过，应使用 $\texttt{cnt.find("Wang")}$ 。若改为读取 $\texttt{cnt["Wang"]}$ ，而 Wang 原本不存在，map 就会新建一条次数为 $0$ 的记录。之后再输出不同姓名数，就可能把这个没有出现过的人也算进去。

map 还支持以下操作：

操作	在姓名记录中的含义
$cnt.find(s)$	查找姓名 $s$ ，不会新建记录
$cnt.erase(s)$	删除姓名 $s$ 及其次数，不存在时不改变 map
$cnt.size()$	当前记录了多少个不同姓名，不是所有次数之和

若用 $it$ 保存 $find$ 的结果，这个位置叫作迭代器。确认 $it\ne cnt.end()$ 后， $\texttt{it->first}$ 是姓名， $\texttt{it->second}$ 是对应次数。查找失败时，不能把 $end()$ 当作一条记录读取。

四、set：查找最接近的木材长度

例题：木材仓库

P5250 木材仓库要求按输入顺序处理进货和出货：

操作 1 x：进货一根长度为 $x$ 的木材。若仓库已经有相同长度，输出 Already Exist，不再加入；否则加入仓库。
操作 2 x：要求出货长度为 $x$ 的木材。若仓库为空，输出 Empty；否则取出与 $x$ 最接近的一根，输出实际长度。距离相同时，取较短的一根。

例如仓库有长度为 $10,20$ 的两根木材，要求出货长度为 $15$ 。两根木材与要求长度的距离都是 $5$ ，因此取出较短的 $10$ 。出货以后，仓库只剩长度为 $20$ 的木材。

题目允许用相近的长度代替要求长度，但出货时只能取一根，而且取出后必须从库存中删除。

直接扫描库存，找出距离最小的一根

可以先用数组保存当前库存。进货时扫描数组，检查有没有相同长度；出货时扫描数组，比较每根木材与要求长度 $x$ 的距离。

设正在检查的木材长度为 $y$ ，距离就是 $|y-x|$ 。扫描时记住目前最合适的一根：遇到距离更小的就换成它；距离相同，则比较长度，保留较短的。扫描结束后，输出并删除选中的木材。

按照这个办法，手算一组操作：

操作	输出	操作后的库存
`1 10`	无	$\{10\}$
`1 20`	无	$\{10,20\}$
`1 20`	`Already Exist`	$\{10,20\}$
`2 15`	$10$	$\{20\}$
`1 8`	无	$\{8,20\}$
`2 19`	$20$	$\{8\}$
`2 8`	$8$	$\varnothing$
`2 6`	`Empty`	$\varnothing$

其中要求 $15$ 时，实际取出的是 $10$ ，因此删除的是 $10$ ，不是要求长度 $15$ 。后面的查询都应使用出货后的库存。

这个做法每次都可能扫描全部库存。设总操作数为 $m$ ，库存最多有 $m$ 根，一次操作需要 $O(m)$ 时间，全部操作最坏需要 $O(m^2)$ 时间。本题最多有 $10^5$ 次操作，每次都扫描库存会产生过多的比较。

如果把长度排好序，就可以用二分查找要求长度附近的木材。但库存不断进货、出货，普通数组为了保持有序，插入和删除时仍可能移动大量元素。因此，需要既能保持长度有序，又能快速插入、删除和查找的容器。

长度有序时，只需比较要求长度两边最近的木材

先考虑已经按长度排好的库存。要求长度为 $x$ ，把库存分成“小于 $x$ ”和“不小于 $x$ ”两部分：

小于 $x$ 的木材中，长度最大的那根离 $x$ 最近。更短的木材只会离 $x$ 更远。
不小于 $x$ 的木材中，长度最小的那根离 $x$ 最近。更长的木材只会离 $x$ 更远。

所以，每边各找出一根，再比较它们的距离即可，不用检查其他木材。如果恰好有长度为 $x$ 的木材，它的距离为 $0$ ，就应取出这一根。

例如库存为 $\{8,14,20\}$ ，要求 $x=17$ 。左边只需考虑 $14$ ，因为 $8$ 更远；右边只需考虑 $20$ 。两根与 $17$ 的距离都是 $3$ ，按规则取出 $14$ 。

把左边的长度记为 $a$ ，右边的长度记为 $b$ 。由于 $a<x$ 、 $b\ge x$ ，距离分别为 $x-a$ 和 $b-x$ 。当

x-a\le b-x

时选择 $a$ ，否则选择 $b$ 。这里使用 $\le$ ，正好把“距离相同取较短的一根”写进了判断中。

左边这根通常称为前驱；右边找到的第一个不小于 $x$ 的长度，是本次查询的后继候选。这些名称指的就是刚才两边最近的木材。

用 set 保持库存有序，并查找右边第一根

前面用 set 查找排除名单时，只关心某个姓名是否存在。set 还有一个重要性质：元素按大小有序。把木材长度放进 set，就能在进货和出货后继续按长度查找。

前面学过的优先队列只能直接读取最小值或最大值，这里要找的却是某个要求长度附近的木材。例如库存为 $\{8,14,20\}$ 、要求 $17$ 时，应取出中间的 $14$ 。只知道库存的最小值和最大值还不够。

set<int> s;

$s$ 保存当前库存中每根木材的长度。set 不保留重复值，正好符合本题“相同长度只保留一根”的要求。进货时先用 $s.find(x)$ 判断长度是否已经存在；存在则输出重复提示，否则用 $s.insert(x)$ 插入。

出货需要找右边第一根，也就是第一个不小于 $x$ 的长度。set 的 $lower\_bound$ 正好完成这一步：

auto it=s.lower_bound(x);

$it$ 保存找到的位置，叫作迭代器。如果找到实际木材，用 $\texttt{*it}$ 读取它的长度；如果没有任何长度不小于 $x$ ，则 $it=s.end()$ ，表示查找结果越过末尾。

在库存 $\{8,14,20\}$ 中查找 $17$ ， $it$ 指向 $20$ 。复制一份位置 $jt=it$ ，再执行 $\texttt{--jt}$ ，就移到前一根 $14$ 。这样，就找到了需要比较的两根木材。

先处理空仓和缺少一边的情况

两边不一定都有木材。例如要求长度比所有库存都短，就没有左边那根；要求长度比所有库存都长，就没有右边那根。

$s.begin()$ 是最短木材的位置， $s.end()$ 是越过最后一根的位置。仓库为空时，两者相等。 $end()$ 本身没有木材，不能直接读取；仓库非空时，可以从 $end()$ 向前移动一次，找到最后一根，也就是最长的木材。

因此，按下面的顺序处理：

情况	怎样选择	例子
仓库为空	输出 `Empty`，结束本次操作	没有任何库存
$it=s.end()$	没有右边的木材，选最后一根	库存 $\{8,14,20\}$ ，要求 $25$ ，选 $20$
$it=s.begin()$ ，且仓库非空	没有左边的木材，选 $it$ 指向的这一根	库存 $\{8,14,20\}$ ，要求 $5$ ，选 $8$
其他情况	比较 $it$ 和它前一根的距离	库存 $\{8,14,20\}$ ，要求 $17$ ，选 $14$

代码中先检查空仓，才允许从 $end()$ 向前移动；先确认 $it$ 不是 $begin()$ ，才允许寻找前一根。选定后， $it$ 必须指向一根实际存在的木材，再输出 $\texttt{*it}$ ，用 $s.erase(it)$ 删除这一根。

操作	在本题中的作用
$s.find(x)$	查找是否有长度为 $x$ 的木材，没有时返回 $s.end()$
$s.insert(x)$	加入长度为 $x$ 的木材
$s.lower\_bound(x)$	查找第一根长度不小于 $x$ 的木材
$s.erase(it)$	删除 $it$ 指向的那根木材
$s.empty()$	判断仓库是否为空

如果按长度删除，也可以使用 $s.erase(x)$ ；但本题出货可能取出与 $x$ 不同的长度，已经找到实际位置时，直接按位置删除更合适。

木材仓库参考程序

输入第一行是操作数 $m$ ，接下来每行是 1 x 或 2 x。原题操作数不超过 $10^5$ ，长度是正整数且不超过 $10^9$ 。两个长度的差在 $\texttt{int}$ 范围内。

#include <bits/stdc++.h>
using namespace std;
set<int> s;

int main(){
    int m;
    cin>>m;
    for(int i=1;i<=m;++i){
        int op,x;
        cin>>op>>x;
        if(op==1){
            if(s.find(x)!=s.end())cout<<"Already Exist\n";
            else s.insert(x);
        }else{
            if(s.empty()){
                cout<<"Empty\n";
                continue;
            }
            // 只比较不小于 x 的第一个长度和它的前驱。
            auto it=s.lower_bound(x);
            if(it==s.end())--it;
            else if(it!=s.begin()){
                auto jt=it;
                --jt;
                if(x-*jt<=*it-x)it=jt;
            }
            cout<<*it<<'\n';
            s.erase(it);
        }
    }
    return 0;
}

进货时，相同长度不重复加入；出货时，两边最近的木材中一定包含应该取出的那根。选定后删除实际木材，因此 $s$ 中保存的始终是操作完成后的库存。

每次进货或出货只进行常数次 set 操作，不再扫描全部库存。库存最多有 $m$ 根，查找和插入的时间为 $O(\log(m+1))$ ，删除也不会超过这个时间。因此，总时间为 $O(m\log(m+1))$ ，空间为 $O(m)$ 。

补充：如果允许相同长度的木材

若仓库允许多根木材长度相同，就要分别保存它们。此时可改用 multiset，并在进货时直接插入，不再拒绝重复长度。

出货时仍然每次只取一根。按值执行 $s.erase(x)$ 会删除全部长度为 $x$ 的木材，而按迭代器执行 $s.erase(it)$ 只删除指向的那一根。因此，即使库存中有两根长度为 $10$ 的木材，第一次取出 $10$ 后，也应保留另一根。

五、把操作要求对应到容器

题目要求	适合的保存方式	还需要明确的信息
最近加入的先处理	栈	栈中元素表示尚未完成的什么任务
最早加入的先处理	队列	入队顺序是否就是处理顺序
候选动态变化，每次取最值	优先队列	优先规则及相同优先级时的规则
按姓名、编号等关键字保存对应值	map	值是次数、位置、成绩还是其他信息
保存不同元素，并查找前驱、后继	set	是否允许重复，空集合怎样处理
小而固定的整数值域	数组标记或计数	下标范围与记录含义

“按首次出现顺序输出”属于另外的输出要求。map 和 set 默认按关键字顺序排列，需要时应另存出现顺序，不能把查找顺序当作输出顺序。

六、练习

基础巩固与独立迁移

题目	本题新增的要求	编码前先确定
P3378 堆	插入、读取最小值、删除最小值分别由不同操作执行	读取最小值是否应该改变堆；重复最小值删除几个
P1918 保龄球	根据瓶子数查询对应的原位置，不存在时输出 $0$	map 的键应该是瓶子数还是位置；查询不存在的键是否需要插入
P5266 学籍管理	同名记录要更新，还要支持查询、删除和输出人数	修改是否增加人数；失败查询是否改变已有记录数

保龄球题保证各位置的瓶子数不同，完整数据中数值可达 $10^9$ ，不适合直接按瓶子数开数组。若这个保证取消，还需重新确定一个瓶子数对应多个位置时怎样回答查询。

对照已有例题修改条件

姓名统计改为按字典序输出，能否去掉首次出现顺序表？若改为按次数从多到少输出，同次数时按字典序，应该保存并比较哪些信息？
优先级任务改为“同优先级时编号较大的先处理”，pair 中两个数应怎样选择，才能继续使用默认大根堆？输出编号时是否还需要取相反数？
木材仓库允许重复长度，但每次只取出一根。改用 multiset 后，哪些判断和删除操作需要变化？用两根长度均为 $10$ 的木材，手算连续三次出货的结果。