小明的账单（信息学奥赛一本通- P1372）
【题目描述】
小明在一次聚会中，不慎遗失了自己的钱包，在接下来的日子，面对小明的将是一系列的补卡手续和堆积的账单… 在小明的百般恳求下，老板最终同意延缓账单的支付时间。可老板又提出，必须从目前还没有支付的所有账单中选出面额最大和最小的两张，并把他们付清。还没有支付的账单会被保留到下一天。 请你帮他计算出支付的顺序。
【输入】
第1行：一个正整数N(N≤15,000)，表示小明补办银联卡总共的天数。
第2行到第N+1 行：每一行描述一天中收到的帐单。先是一个非负整数M≤100，表示当天收到的账单数，后跟M个正整数（都小于1,000,000,000），表示每张帐单的面额。
输入数据保证每天都可以支付两张帐单。
【输出】
输出共N 行，每行两个用空格分隔的整数，分别表示当天支付的面额最小和最大的支票的面额。
【输入样例】
4 3 3 6 5 2 8 2 3 7 1 7 0【输出样例】
3 6 2 8 1 7 5 7这是一个非常经典的“动态维护极值”问题。既然题目不难，我们直接切入重点，对比两种解法的优劣和核心技巧。
1. 题目本质
我们需要维护一个账单池，支持以下三种操作，且每天都要执行：
Insert：插入若干个新数值。
Pop Max：查询并删除最大值。
Pop Min：查询并删除最小值。
2. 解法一：STL Multiset（最简捷）
利用 C++multiset底层红黑树自动排序的特性，它是解决此类问题的“万能钥匙”。
思路：所有数据丢进去，它自动排好序。
最小值：
*st.begin()最大值：
*st.rbegin()
代码优势：极短，逻辑极其简单，不易出错。
关键避坑：
删除时必须用迭代器
st.erase(it)，绝不能用st.erase(val)。后者会把所有同金额的账单一次性删光，导致 BUG。删除最大值推荐用
st.erase(prev(st.end()))。
3. 解法二：双堆 + 懒惰删除（最高效）
利用两个优先队列分别维护最大值和最小值。这是解决“堆不支持随机删除”的标准范式。
思路：
双倍存储：每个账单同时进入
maxq和minq，并绑定唯一id。懒惰删除 (Lazy Deletion)：
当我们在 maxq 删除了一个元素，无法直接去 minq 里删它（太慢）。
于是我们在 deleted 数组里标记该 id 为“已删除”。
等到 minq 的堆顶恰好浮现出这个“已删除”的元素时，再把它弹出丢掉。
工程细节：
while循环清理“死元素”时，最好加上!q.empty()防止越界（虽然本题数据保证不空，但这是好习惯）。
4. 总结与对比
| 维度 | Multiset 解法 | 双堆 + 懒惰删除 解法 |
| 代码量 | 极少 | 中等 |
| 思维难度 | 无脑 | 需理解延迟删除 |
| 运行效率 | 较慢 (红黑树常数大) | 极快(堆操作常数小) |
| 适用场景 | 比赛省时间、数据量中等 | 卡常数、追求极致性能 |
完整代码
/* //直接用multiset 可以直接得到最大值和最小值 #include <iostream> #include <set>//必须包含这个头文件 #include <algorithm> using namespace std; //使用multiset,因为它会自动排序,且允许有重复的账单金额 multiset<int>st; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ int cnt;cin>>cnt; //1.把今天的账单全部扔进set for(int j=1;j<=cnt;j++){ int tmp; cin>>tmp; st.insert(tmp);//O(log N)自动排序 } //2.取出并删除最小值 //st.begin()就是最小值的迭代器 int mi=*st.begin(); st.erase(st.begin());//注意:要用迭代器删除,否则会删除所有等于mi的元素 //3.取出并删除最大值 //st.rbegin()是反向迭代器的开始,指向最大值 //或者用prev(st.end())也可以找到最大值 int ma=*st.rbegin(); //删除最大值(需要将反向迭代器转为正向迭代器,或者直接删除尾部前一个) //最简单的写法是删除迭代器:prev(st.end())指向最后一个元素 st.erase(prev(st.end())); //输出 cout<<mi<<" "<<ma<<"\n"; } return 0; } */ //用优先队列 #include <iostream> #include <queue> using namespace std; int deleted[1500001]; priority_queue<pair<int,int>> maxq;//默认最大堆 priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> minq;//最小堆 int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin>>n; int id=0; for(int i=1;i<=n;i++){//总共有n天 int cnt;//每天有cnt张账单 cin>>cnt; for(int j=1;j<=cnt;j++){ int val; cin>>val; id++; maxq.push({val,id}); minq.push({val,id}); } while(!maxq.empty() && deleted[maxq.top().second]==1){//如果最大堆堆顶的数的id已经被标记为在最小堆里删除了，就直接弹出 maxq.pop();//如果最大堆堆顶的数的id已经被标记为在最小堆里删除了，就直接弹出 } int ma=maxq.top().first;//最大堆的最大值 deleted[maxq.top().second]=1;//标记这个最大值的id为1（已被删除，后面不能被最小堆拿来用了） maxq.pop();//把最大堆的最大值弹出 while(!minq.empty() && deleted[minq.top().second]==1){//如果最小堆堆顶的数的id已经被标记为在最大堆里删除了，就直接弹出 minq.pop();//如果最小堆堆顶的数的id已经被标记为在最大堆里删除了，就直接弹出 } int mi=minq.top().first;//最小堆的最小值 deleted[minq.top().second]=1;//标记这个最小值的id为1（已被删除，后面不能被最大堆拿来用了） minq.pop(); cout<<mi<<" "<<ma<<" "<<"\n"; } return 0; }在比赛中，如果时间允许（N<=10^5），优先用 Multiset ；如果数据量极大或时限很紧，必须掌握双堆+懒惰删除。