STL多重集合multiset

网友投稿 1306 2022-11-12

STL多重集合multiset

STL多重集合multiset

导语:今天看IOI2004的论文集,学到了一种集合函数,顺便把它记录下来,一位很牛的学长关于此集合写的很详细,可以参考他的博客链接​​click here~~​​

例题:支付帐单:

题目描述

比尔最近遇到了一件麻烦事。每天上午,他会收到若干张帐单(也可能一张也没收到),每一张都有一定的面额。下午,他会从目前还没有支付的帐单中选出面额最大和最小的两张,并把它们付清。还没有支付的帐单会被保留到下一天。现在比尔已经知道他每天收到帐单的数量和面额,请你帮他给出支付的顺序。

约束条件 天数的上限为30,000,每天至少有两张可支付的帐单,保证最后一天全部付清

【输入格式】 第1 行:一个正整数N(N≤30,000),表示总共的天数。 第2 行到第N+1 行:每一行描述一天中收到的帐单。先是一个非负整数M,表示当天 收到的账单数,后跟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

【思路分析】

从数据范围来看,帐单的接收和支付要在O(log n)或以下完成。

思路一:

建一个最大堆和一个最小堆,并在相应元素之间建立映射。

思路二:

建一棵平衡二叉树。用STL中的多重集合multiset来实现。

/*

关联容器的multiset函数

*/

代码实现:

#include using namespace std;#include #include #include #include #include #include int main(){ int n,m,p; multisetbills;//可重复的多元集合 cin>>n; while(n--) { cin>>m; while(m--) { cin>>p; bills.insert(p);//插入一次自动排序一次 } cout<<*bills.begin()<<" "<<*(--bills.end())<

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:ZOJ Monthly, October 2011 (DP+数学专场!!!)
下一篇:开始闭关~~跟水题说拜拜~~
相关文章

 发表评论

暂时没有评论,来抢沙发吧~