[基础] 学习笔记
1. 重载运算符
struct node
{
int x;
bool operator < (const node & a) const
{
return x > a.x; // 从小到大
}
};
priority_queue< node > q;
struct cmp
{
bool operator()(const int & a, const int & b)
{
...
}
};
priority_queue< int, vector<int>, cmp > q;
2. 二分
在单调递增序列 \(a\) 中查找 第一个 \(\geqslant x\) 的数，即 \(x\) 或 \(x\) 的后继。
while (l < r)
{
int mid = (l + r) >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
return a[l];
在单调递增序列 \(a\) 中查找 第一个 \(\leqslant x\) 的数，即 \(x\) 或 \(x\) 的前驱。
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (a[mid] <= x) l = mid;
else r = mid - 1;
}
return a[l];