CSU 1554 SG Value (集合类的学习)
题目大意:
2种操作
1 a:往集合中添加一个元素a
2: 询问这个集合中的元素任意组合相加所不能得到的最小数的值
这道题总是不断地去找当前所能处的最小值能否被当前的最小值加上其前部的一堆可抵达数到达当前位置
也就是 minn < *s.begin() , 说明此时内部最小的元素是不影响这个值的,否则 minn+=*s.begin(),然后剔除最小值,不断往下访问
在这里因为相同数据也可以同时保存在集合内,所以不采用set(会删除重复元素),而是使用multiset。
在这里顺便学习理解一下multiset类的使用
Set、multiset都是集合类,差别在与set中不允许有重复元素,multiset中允许有重复元素
1.增加,删除函数
pair<iterator,bool> insert( x):插入元素x
iterator insert(iterator it,x):在迭代器it处插入元素x
void insert(const value_type *first,const value_type *last):插入[first, last)之间元素
iterator erase(iterator it):删除迭代器指针it处元素
iterator erase(iterator first,iterator last):删除[first, last)之间元素
size_type erase(const Key& key):删除元素值等于key的元素
我们尽量在函数中利用指针来作为参数
2.遍历函数
iterator begin():返回首元素的迭代器指针
iterator end():返回尾元素的迭代器指针
reverse_iterator rbegin():返回尾元素的逆向迭代器指针
reverse_iterator rend():返回首元素前一个位置的迭代器指针
3. 操作函数
const_iterator lower_bound(const Key& key):返回容器中大于等于key的迭代器指针
const_iterator upper_bound(const Key& key):返回容器中大于key的迭代器指针
int count(const Key& key) const:返回容器中元素等于key的元素的个数
pair<const_iterator,const_iterator> equal_range(const Key& key) const:返回容器中元素值等于key的迭代指针[first, last) const_iterator find(const Key& key) const:查找功能,返回元素值等于key的迭代器指针
void swap(set& s):交换集合元素
void swap(multiset& s):交换多集合元素
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
#define ll long long
multiset<int> s; int main()
{
int n , op , v;
while(scanf("%d" , &n) != EOF)
{
while(!s.empty()) s.erase(s.begin());
ll minn=;
for(int i= ; i<n ; i++){
scanf("%d" , &op);
if(op == ){
scanf("%d" , &v);
s.insert(v);
}
else{
while(!s.empty() && minn>=*s.begin()){
minn += *s.begin();
s.erase(s.begin());
}
printf("%lld\n" , minn);
}
}
}
return ;
}
最新文章
- &#39;scrapyd-deploy&#39; 不是内部或外部命令,也不是可运行的程序 或批处理文件。
- C# 文件操作 把文件读取到字节数组
- A/B测试
- [麦先生]LINUX常用命令总结
- (转)linux运行tomcat时JRE_HOME显示不对怎么办?
- WCF的行为与异常-------配置文件说明
- 深入探究VC —— 链接器link.exe(4)
- C语言 九九乘法表
- Java中的强引用和弱引用
- 使用eclipse初步学习vue.js基础==》v-for的使用 ②
- prometheus排错
- TF-IDF原理与实现
- 报名 | 蚂蚁金服ATEC科技大会 &#183; 上海:数字金融新原力
- c 编译和链接过程
- 自定义select 小三角
- Eclemma的安装
- HDU 1022 Train Problem I(栈的操作规则)
- memory引擎和innodb引擎速度对比
- django(python manage.py migrate)同步数据库出错后的解决办法
- rabbitMq视频教程