算法-集合的使用

 1、set常用操作

set<int> q;     //以int型为例 默认按键值升序
set<int,greater<int>> p;  //降序排列 
int x;
q.insert(x);	//将x插入q中
q.erase(x);		//删除q中的x元素,返回0或1,0表示set中不存在x
q.clear();		//清空q
q.empty();		//判断q是否为空，若是返回1，否则返回0
q.size();		//返回q中元素的个数
q.find(x);		//在q中查找x，返回x的迭代器，若x不存在，则返回指向q尾部的迭代器即 q.end()
q.lower_bound(x); //返回一个迭代器，指向第一个键值不小于x的元素
q.upper_bound(x); //返回一个迭代器，指向第一个键值大于x的元素q.rend();		  //返回第一个元素的的前一个元素迭代器
q.begin();		  //返回指向q中第一个元素的迭代器q.end();		 //返回指向q最后一个元素下一个位置的迭代器
q.rbegin();		 //返回最后一个元素

2、set单元素应用

#include<iostream>
#include<set>
using namespace std;
int main()
{set<int> q;   //默认按升序排列 q.insert(5);q.insert(5);q.insert(5);cout<<"q.size "<<q.size()<<endl;   //输出 1 ,在set插入中相同元素只会存在一个q.clear(); //清空setcout<<"q.size "<<q.size()<<"\n\n";q.insert(4);q.insert(4);q.insert(3);q.insert(3); q.insert(2);q.insert(1);cout<<"lower_bound "<<*q.lower_bound(3)<<endl;  //返回3 cout<<"upper_bound "<<*q.upper_bound(3)<<"\n\n";  //返回4 set<int>::iterator i;for( i=q.begin();i!=q.end();i++)   //set的遍历 cout<<*i<<" ";				   //输出1 2 3 4，可见自动按键值排序 cout<<endl;q.erase(4);  //删除q中的 4 for(i=q.begin();i!=q.end();i++)  //再次遍历set 只输出 1 2 3 cout<<*i<<" ";cout<<"\n\n"; set<int,greater<int>> p;  //降序排列 p.insert(1);p.insert(2);p.insert(3);p.insert(4);p.insert(5);for(i=p.begin();i!=p.end();i++)cout<<*i<<" ";cout<<endl;return 0;
}

 3、set的应用

 E-种类数_牛客小白月赛117

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll> s; // 使用集合来存储数组中的非零元素，集合会自动排序
bool exist0 = 0; // 标记数组中是否存在0
int main() {ll ans = 0; // 记录操作轮数ll dec = 0; // 记录已经减去的总和ll n;cin >> n;while (n--) {ll temp;cin >> temp;if (temp != 0) s.insert(temp); // 将非零元素插入集合else exist0 = 1; // 如果有0，标记exist0为1}// 如果集合中只有一个元素且没有0，说明已经所有数相同，不需要操作if (s.size() == 1 && !exist0) {cout << 0 << endl;return 0;}// 当集合中还有元素时，继续操作while (s.size()) {ll num = *s.begin() - dec; // 获取当前最小的非零元素，减去已经减去的总和ll cnt = exist0 ? s.size() + 1 : s.size(); // 如果存在0，种类数为集合大小加1，否则为集合大小ll t = (num + cnt - 1) / cnt; // 计算需要减去的次数，向上取整dec += t * cnt; // 更新已经减去的总和ans += t; // 增加操作轮数s.erase(*s.begin()); // 移除当前最小的元素exist0 = 1; // 标记存在0}cout << ans << endl;return 0;
}