【题单】对顶堆
数据结构题单 2102. 序列顺序查询 维护一个小顶堆 q1，代表前 k 大的元素。 维护一个大顶堆 q2，代表其它元素。 当新加一个元素的时候，首先加入 q2，当 q1 中不足 k 个元素的时候，把 q2 的最大元素移动到 q1。如果 q1 的堆顶小于 q2 的堆顶，此时应该交换堆顶，这个交换操作在一次函数调用中最多会发生一次，因为新加入元素的时候，只会产生一个元素的变化。 另外需要注意自定义对象的比较函数的时候，因为是求第 k 大，并且字典序最小，应该让分数正序排序，名字逆序排序，这样当分数相同的时候，靠后的是字典序更小的。 class SORTracker { public: struct node { int val; string name; bool operator<(const node &rh) const { if (val != rh.val) return val < rh.val; return name > rh.name; } bool operator>(const node &rh) const { if (val != rh.val) return val > rh.val; return name < rh.name; } }; pqg<node> q1; pq<node> q2; int cur; SORTracker() : q1{}, q2{}, cur{1} {} void add(string name, int score) { node tmp = {score, name}; q2.push(tmp); while (SZ(q1) < cur && nemp(q2)) { q1.push(q2.top()); q2.pop(); } while (nemp(q1) && nemp(q2) && q1.top() < q2.top()) { auto t1 = q1.top(); q1.pop(); auto t2 = q2.top(); q2.pop(); q1.push(t2); q2.push(t1); } } string get() { while (SZ(q1) < cur && nemp(q2)) { auto t = q2.top(); q1.push(t); q2.pop(); } cur++; return q1.top().name; } }; 题解区的神奇思路。 ...