28 · 双端队列与优先队列

第一步：每个函数自己是有序的。a_i ＞ 0，抛物线开口向上，对称轴在 x = −b_i/(2a_i) ＜ 0，所以整数部分 x ≥ 1 整段都落在增区间上：F_i(1) ≤ F_i(2) ≤ F_i(3) ≤ …。这一步把“无穷多个值”变成了“一条递增序列”。

第二步：问题变成 n 路归并。每个函数贡献一条递增序列，全局前 m 小就是这 n 条序列归并后的前 m 项。这和第 17 节合并果子是同一个结构：每一步在 n 个候选里取最小。

第三步：候选只需要 n 个。对第 i 个函数，只把“它当前还没输出的最小项”放进堆。堆顶就是全体候选的最小值，输出它，然后让这个函数往前走一格（x 加 1）再放回去。其他函数的候选没变，不用动。

为什么不会漏。堆里始终装着每条序列“尚未输出部分”的首元素。全局最小必然等于某条序列尚无输出的首元素，所以它一定在堆里 —— 取堆顶就是取全局最小。

为什么只推进 m 次。输出 m 个数就结束；每个函数最多被推进 m 次，堆的大小恒为 n，总复杂度 O((n + m) log n)。n = m = 10⁴ 时是 2×10⁴ 次堆操作、每次约 14 次比较，总共几十万次比较，可以忽略不计。

// 核心只有三步：取堆顶 -> 输出 -> 同一函数推进一格
Node cur = pq.top();
pq.pop();
cout << cur.val << '\n';
int nx = cur.x + 1;                   // 只推进这一个函数，别的候选不动
long long nv = f[cur.id].a * nx * nx + f[cur.id].b * nx + f[cur.id].c;
pq.push({nv, cur.id, nx});

问题：n 个数里找出最大的 k 个（k 远小于 n），n 可以到 10⁶。排序是 O(n log n)，而只留 k 个候选可以做到 O(n log k)。

做法：维护一个大小为 k 的小根堆。堆顶是“当前第 k 大”，也就是候选里最差的那个。新来的数只有比堆顶大，才可能挤进前 k，于是弹掉堆顶、把新数放进去；否则直接扔掉。

为什么这样对：扫描到任意位置时，堆里恰好是“已扫描部分最大的 min(k, 已扫描个数) 个”。归纳一步：新数 x 若 ≤ 堆顶，则堆里已有 k 个数 ≥ 堆顶 ≥ x，x 挤不进前 k（最多与第 k 名并列）；若 x ＞ 堆顶，堆顶是 k 个里最差的，用 x 换掉它，剩下的仍然是最大的 k 个。

// n 个数里最大的 k 个，按降序输出
priority_queue<int, vector<int>, greater<int>> q;   // 小根堆，堆顶 = 第 k 大
for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if ((int)q.size() < k) q.push(x);               // 前 k 个直接进
    else if (x > q.top()) {                         // 只有更大才值得换
        q.pop();
        q.push(x);
    }
}
vector<int> ans;
while (!q.empty()) { ans.push_back(q.top()); q.pop(); }   // 弹出是升序
reverse(ans.begin(), ans.end());                   // 翻成降序

两个必须记住的细节：①堆的大小没到 k 时不能读 q.top()（空堆 RE），所以先判 size；②求“最小的 k 个”时方向完全反过来 —— 用大根堆，堆顶是第 k 小，条件是 x ＜ 堆顶。堆顶永远是“当前候选里最差的那个”，被替换的永远是它。

代价对比：n = 10⁶、k = 10 时，log k ≈ 3.3，总比较约 3.3×10⁶ 次；排序要 2×10⁷ 次，差一个量级。k 接近 n 时两者差不多，直接 sort 更省事。

模型：n × m 的网格，每格有权 0 或 1。从左上角走到右下角，每步上下左右，进入一格的代价等于该格的权值，求最小总代价。

普通 BFS 不行。BFS 的正确性依赖“先发现的更近”，而这里边权有 0：同一个点可能被一条长路先发现（层数多），却被一条短路后到达（总代价小）。层数和距离脱钩了。

Dijkstra 行，但贵。nm 个点各有一个 dist，每次取最小要堆，复杂度 O(nm log(nm))。可是这里边权只有 0 和 1，dist 的最小值只有两种可能：当前值 d，或 d + 1。两种值只需要两个“桶”，而 deque 恰好能当两个桶用 —— 这就是 0-1 BFS。

规矩只有两条：从队头取点 u 扩展；若走到 v 的边权是 0，把 v push_front，若是 1，把 v push_back。

为什么队头一定是最小的。设当前 dq 里的距离序列非递减，且只含 d 与 d + 1 两种值。从队头取出 dist = d 的点 u：边权 0 的新点距离也是 d，插到队头不破坏非递减；边权 1 的新点距离是 d + 1，插到队尾也不破坏非递减。两条规矩都是为了保住这个不变式。于是每次取出的都是当前最小，和 Dijkstra 一样，只是“堆”退化成了两个桶。

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
const int INF = 0x3f3f3f3f;
int n, m;
int w[N][N], d[N][N];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            cin >> w[i][j];
            d[i][j] = INF;
        }

    deque<int> dq;                       // 存编号 x*m+y，省一个 pair 的拷贝
    d[0][0] = 0;
    dq.push_front(0);                    // 源点距离最小，从队头进
    while (!dq.empty()) {
        int id = dq.front();
        dq.pop_front();
        int x = id / m, y = id % m;      // 注意除的是列数 m，不是行数 n
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            int nd = d[x][y] + w[nx][ny];
            if (nd >= d[nx][ny]) continue;   // 不比已知更优，就不必再进队
            d[nx][ny] = nd;
            if (w[nx][ny] == 0) dq.push_front(nx * m + ny);   // 0 边：插队头
            else                dq.push_back(nx * m + ny);    // 1 边：排队尾
        }
    }
    cout << d[n - 1][m - 1] << '\n';
    return 0;
}