洛谷 P1440 求 m 区间内的最小值

// P1440 求 m 区间内的最小值 —— ★ 这一版就能 AC
//
// 求每一项**之前** m 个数的最小值：第 i 行输出 min(a[max(1, i−m)] … a[i−1])，
// 前面一个数都没有（i = 1）就输出 0。
//
// ★★ 和本章第 9 步那道模板题只差一件事：**窗口不含自己，而且落在自己左边**。
//   ⇒ 顺序变成「先输出，再把 a[i] 放进队列」——
//   这两行的次序就是这道题唯一的关卡（本页第 ② 步）。
//
// ★ 题面那句「若前面没有数则输出 0」＋「1 ≤ aᵢ」，等于**直接把哨兵送给你了**
//   —— 和同一章的 [P1886](/sol/p1886/)（题面把 int 用光、一个哨兵都不剩）正好相反。
#include <bits/stdc++.h>
using namespace std;

static const int N = 2000006;
static int a[N], q[N];

static char ibuf[1 << 16];
static int ipos, ilen;
static inline char gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return 0; }
    return ibuf[ipos++];
}
static inline int rd() {
    char c = gc();
    while (c && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}
static char obuf[1 << 16];
static int opos;
static inline void flushOut() { fwrite(obuf, 1, opos, stdout); opos = 0; }
static inline void pc(char c) { if (opos == (int)sizeof(obuf)) flushOut(); obuf[opos++] = c; }
static inline void wr(int x) {
    if (!x) { pc('0'); return; }
    char t[12];
    int c = 0;
    while (x) { t[c++] = char('0' + x % 10); x /= 10; }
    while (c) pc(t[--c]);
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; i++) a[i] = rd();

    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && q[head] < i - m) head++;   // 窗口是 [i−m, i−1]
        wr(head <= tail ? a[q[head]] : 0);                // ★ 先输出
        pc('\n');
        while (head <= tail && a[q[tail]] >= a[i]) tail--;
        q[++tail] = i;                                    // ★ 再入队
    }
    flushOut();
    return 0;
}

// P1440 · 错法 ②：把「前面不足 m 项」读成了「前面不足 m 项就输出 0」
//
// 题面原话是两句：
//   「若前面的数不足 m 项**则从第 1 个数开始**」——  不足也要算，只是窗口短一点；
//   「若前面**没有数**则输出 0」                 ——  只有第 1 项才输出 0。
// ⇒ 把两句读成一句，就成了「前 m 项全输出 0」。
// ★ m = 1 时这两种读法**完全一样**（只有第 1 项没有前驱）⇒ 那一档是**能证的精确 0**。
#include <bits/stdc++.h>
using namespace std;

static const int N = 2000006;
static int a[N], q[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    string out;
    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && q[head] < i - m) head++;
        out += to_string(i <= m ? 0 : a[q[head]]);        // ✗ 前 m 项一律 0
        out += '\n';
        while (head <= tail && a[q[tail]] >= a[i]) tail--;
        q[++tail] = i;
    }
    cout << out;
    return 0;
}

// P1440 · 错法 ③：出窗那句差一 —— 窗口短了一个
//
//   while (head <= tail && q[head] <  i − m) head++;   ← 正解（窗口 [i−m, i−1]，共 m 个）
//   while (head <= tail && q[head] <= i − m) head++;   ← 这一版（窗口 [i−m+1, i−1]，共 m−1 个）
//
// ★ 这是本章第 10 步那句「边界比模板本身更容易写错」在这道题上的样子：
//   窗口的两端都被题面挪了一格，于是那个 `<` 到底该不该带等号，**只能重新推一遍**。
#include <bits/stdc++.h>
using namespace std;

static const int N = 2000006;
static int a[N], q[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    string out;
    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && q[head] <= i - m) head++;   // ✗ 多了个等号
        out += to_string(head <= tail ? a[q[head]] : 0);
        out += '\n';
        while (head <= tail && a[q[tail]] >= a[i]) tail--;
        q[++tail] = i;
    }
    cout << out;
    return 0;
}

// P1440 · 错法 ①：把自己也算进了窗口
//
//   两行的次序反了：先把 a[i] 放进队列，再输出 ⇒ 窗口成了 [i−m, i]。
// ⚠ 这就是把本章第 9 步那道模板题的代码**原样搬过来**的结果 ——
//   那道题的窗口**含**当前元素，这道题**不含**。
// ⇒ 触发条件一句话：**a[i] 比它前面 m 个数里最小的还小**。
#include <bits/stdc++.h>
using namespace std;

static const int N = 2000006;
static int a[N], q[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    string out;
    int head = 1, tail = 0;
    for (int i = 1; i <= n; i++) {
        while (head <= tail && q[head] < i - m) head++;
        while (head <= tail && a[q[tail]] >= a[i]) tail--;
        q[++tail] = i;                                    // ✗ 先入队
        out += to_string(a[q[head]]);                     // ✗ 再输出
        out += '\n';
    }
    cout << out;
    return 0;
}