algo-aha

自定义比较的priority_queue

auto cmp = [](const vector<int> &a, const vector<int> &b) { 
  return a[0] < b[0]; // priority_queue用less是最大堆
};
priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> taken(cmp);

另：用multiset作为可支持删除的优先队列

二分搜索函数lower_bound(t)找第一个>=t的位置

// nums中找第一个>=t的位置
auto it = lower_bound(nums.begin(), nums.end(), t);
// 第一个<=t的位置
auto it = upper_bound(nums.begin(), nums.end(), t); // >t的位置
prev(it, 1); // 回退一位，就是<=t的位置

随机数

构造函数中：srand(time(NULL));
使用时：rand() % 10 // 生成[0..9]

自定义比较的set

struct Cmp {
    bool operator()(const Interval &a, const Interval &b) { 
        // 若有插入操作，st的比较函数一定要写全各子段，否则插入只根据部分子段就判重
        return a.start < b.start || (a.start == b.start && a.end < b.end);
    }
};
set<Interval, Cmp> st;

或者比较函数写在Interval结构中

struct Inteval {
    int start, end;
    bool operator<(const Interval &rhs) const {
        ...
    }
};
set<Interval> st;

第k小的数

// k是1-based，midptr要加上k-1偏移
auto midptr = nums.begin() + (k-1);
nth_element(nums.begin(), midptr, nums.end());
int median = *midptr;

// 中位数是第(n+1)/2小的数
auto midptr = nums.begin() + (n-1)/2; // (n+1)/2-1=(n-1)/2
// 如果是找第k大的数
nth_element(nums.begin(), midptr, nums.end(), greater<int>());

前k个数排序

partial_sort(A.begin(), A.begin() + K, A.end());

bitset

bitset<10>(h << 6 | m).count()

取绝对值

long x = labs(INT_MIN); // abs(INT_MIN)==INT_MIN，因为溢出

unsigned数中比特1的个数

__builtin_popcount(a)

进制转换

stoi(ab, NULL, 16)