STL使用总结
快排
sort(a+1,a+n+1,less
sort(a+1,a+n+1,greater
堆（queue）
1
分为大根堆priority_queue <int,vector<int>,less<int> > q;（第三个可以省略）
以及小根堆priority_queue <int,vector<int>,greater<int> > q;（第三个不可省略）
2
可以通过对顶堆来实现动态中位数，实现如下
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{
int f=1;x=0;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
template<typename T>inline void wr(T x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)wr(x/10);
putchar(x%10^48);
}
priority_queue <int,vector<int> > q1;
priority_queue <int,vector<int>,greater<int> > q2;
int n;
inline void insert(int x)
{
if(q2.empty())q2.push(x);
else if(x>=q2.top())q2.push(x);
else q1.push(x);
if(q1.size()&&q2.size())while(q1.top()>q2.top())q2.push(q1.top()),q1.pop();
while(q1.size()>q2.size())q2.push(q1.top()),q1.pop();
while(q2.size()-q1.size()>=2)q1.push(q2.top()),q2.pop();
}
signed main()
{
re(n);
for(int i=1;i<=n;i++)
{
int x;
re(x);
insert(x);
if(i%2)wr(q2.top()),putchar('\n');
}
return 0;
}
set（multiset）
特点
set不可重（可用来去重） multiset可重 但都具有有序性
成员函数
\(begin()\) :第一个元素的位置
\(end()\) : 最后一个元素的位置 \(+1\)
\(insert()\) : 插入
\(erase()\) : 删除 ，注意传参既可以是值也可以是迭代器
\(find()\) :查找某个元素的位置，无则返回 \(end()\)
\(lower\)_\(bound()\) :第一个 \(\geq\) 某个值的元素所在位置
\(empty()\) \(size()\) :不多赘述
\(prev(iterator)\)：返回某个迭代器的上一个迭代器
遍历
for(set<int>iterator it=s.begin();it!=s.end();it++)
for(auto it=s.begin();it!=s.end();it++)
for(auto i:s) 这个是直接访问每一个元素，字符串中同样可以使用
结构体
用结构体重载运算符时要加一个 friend 声明
[NOIP2012 提高组] 开车旅行：
点击查看代码
struct Drive
{
int num,h;
friend bool operator<(Drive a,Drive b){return a.h<b.h;}
};