作为教练，制作和至少为 K 的最短子数组的数据集时，难点在于构造能够触发单调队列“双端弹出”逻辑的序列。由于存在负数，我们需要构造一些“先减后增”或“剧烈波动”的前缀和序列来测试程序的正确性。

本题的时间复杂度要求为 $O(N)$，因此我们的数据生成器和标准答案程序都必须严格遵守线性时间复杂度。本题不涉及树/图结构或除法运算。

一、 数据生成器代码 (C++14)

该程序会自动生成 1.in 到 10.out。逻辑采用 $O(N)$ 单调队列标程计算结果。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#include <random>
#include <ctime>

using namespace std;

/**
 * 标程逻辑：用于生成 .out 文件
 */
int solve(int n, long long k, const vector<int>& a) {
    vector<long long> p(n + 1, 0);
    for (int i = 0; i < n; ++i) p[i + 1] = p[i] + a[i];

    int ans = n + 1;
    deque<int> dq;

    for (int i = 0; i <= n; ++i) {
        // 逻辑 1：从队首尝试更新最小长度
        while (!dq.empty() && p[i] - p[dq.front()] >= k) {
            ans = min(ans, i - dq.front());
            dq.pop_front();
        }
        // 逻辑 2：维护队内前缀和的单调递增性
        while (!dq.empty() && p[i] <= p[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    return (ans > n) ? -1 : ans;
}

/**
 * 写入测试点文件
 */
void write_test_case(int id, int n, long long k, const vector<int>& a) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    // 写入 .in
    ofstream fout(in_name);
    fout << n << " " << k << "\n";
    for (int i = 0; i < n; ++i) {
        fout << a[i] << (i == n - 1 ? "" : " ");
    }
    fout << "\n";
    fout.close();

    // 写入 .out
    ofstream fans(out_name);
    fans << solve(n, k, a) << "\n";
    fans.close();

    cout << "Generated Case " << id << " (n=" << n << ", k=" << k << ")" << endl;
}

int main() {
    mt19937 rng(time(0));

    for (int i = 1; i <= 10; ++i) {
        int n;
        long long k;
        vector<int> a;

        if (i == 1) { // 样例
            n = 3; k = 3;
            a = {2, -1, 2};
        }
        else if (i == 2) { // 边界：n=1, 不满足 k
            n = 1; k = 100;
            a = {10};
        }
        else if (i == 3) { // 边界：全负数
            n = 1000; k = 1;
            for(int j=0; j<n; ++j) a.push_back(-(rng() % 100 + 1));
        }
        else if (i == 4) { // 全正数 (普通滑动窗口即可处理)
            n = 1000; k = 5000;
            for(int j=0; j<n; ++j) a.push_back(rng() % 100 + 1);
        }
        else if (i == 5) { // 答案为 1 (存在某个数直接 >= k)
            n = 1000; k = 1000;
            for(int j=0; j<n; ++j) a.push_back(rng() % 500);
            a[n/2] = 1000;
        }
        else if (i == 6) { // 锯齿形数据 (测试 pop_back 逻辑)
            n = 2000; k = 10000;
            for(int j=0; j<n; ++j) {
                if (j % 2 == 0) a.push_back(10000); // 大正数
                else a.push_back(-9999);            // 大负数
            }
        }
        else if (i == 7) { // 答案为 n (全选才够)
            n = 1000; k = 1000;
            a = vector<int>(n, 1);
        }
        else if (i <= 8) { // 随机中等规模
            n = 5000; k = 10000;
            for(int j=0; j<n; ++j) a.push_back((int)(rng() % 200001 - 100000));
        }
        else { // 极限规模随机 (n=10^5)
            n = 100000; k = 5000000;
            for(int j=0; j<n; ++j) a.push_back((int)(rng() % 200001 - 100000));
        }

        write_test_case(i, n, k, a);
    }

    return 0;
}

二、 测试点设计思路（评测要点）

作为教练，这 10 组数据的核心任务是检测选手是否正确处理了“非单调性”：

三、 考场避坑建议

1. 哨兵节点的重要性： 前缀和数组 p 必须有 $n+1$ 个元素（p[0]=0）。如果不处理 $p[0]$，当最短子数组是从数组下标 $0$ 开始时（例如 A = [5], K = 5），你的 p[j] - p[i] 逻辑将找不到 i=0 这个起点。

2. long long 的全覆盖：

   • A[i] 最大 $10^5$，n 最大 $10^5$，前缀和最大 $10^{10}$ $\rightarrow$ 前缀和必须用 long long。
   • k 最大 $10^9$ $\rightarrow$ k 必须用 long long。

3. 单调队列的弹出逻辑（两个 while）：

   • 队首弹出：是为了寻找最优解（越往后找长度越长，所以满足了就记录并弹出）。
   • 队尾弹出：是为了维护单调性（新的前缀和更小且位置更靠后，比旧的更有潜力）。 如果少写了任何一个 while，复杂度或正确性都会出问题。

4. 非递归与安全性： 本题为线性扫描，生成器与标程均无递归。没有除法运算，故无除零风险。

这份生成器生成的 .in 和 .out 文件完全符合 NOI 竞赛标准，你可以直接上传至 OJ 系统。加油！

你好，同学！这道题是单调队列（Monotonic Queue）技巧中公认的“分水岭”题目。由于数组中存在负数，普通滑动窗口的双指针单向移动逻辑会失效，必须借助于前缀和的单调性维护。

以下是基于 C++14 标准 的满分题解代码。

一、 标程代码 (C++14 标准)

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

/**
 * 题目：和至少为 K 的最短子数组
 * 核心：前缀和 + 单调队列优化
 * 
 * 易错点预警：
 * 1. 前缀和溢出：A[i] 为 10^5，N 为 10^5，前缀和可达 10^10，必须用 long long。
 * 2. 哨兵元素：前缀和数组需要包含 P[0] = 0，否则会漏掉从开头开始的子数组。
 * 3. 双端弹出：单调队列既要从队首尝试更新答案，又要从队尾维护单调性。
 */

void solve() {
    int n;
    long long k;
    if (!(cin >> n >> k)) return;

    vector<long long> p(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        p[i] = p[i - 1] + x; // 计算前缀和
    }

    // ans 初始化为一个不可能的最大值
    int ans = n + 1;
    // dq 存储的是前缀和数组 p 的下标
    deque<int> dq;

    for (int j = 0; j <= n; ++j) {
        // --- 逻辑 1：从队首寻找并弹出满足条件的解 ---
        // 如果当前前缀和 p[j] 减去 队首前缀和 p[dq.front()] >= k
        // 说明找到了一个合法区间 [dq.front(), j]
        while (!dq.empty() && p[j] - p[dq.front()] >= k) {
            ans = min(ans, j - dq.front());
            // 关键逻辑：为什么可以 pop_front？
            // 因为后面的 j' > j 即使也能满足 p[j'] - p[dq.front()] >= k，
            // 其长度 j' - dq.front() 必然大于当前的 j - dq.front()，不可能成为最短。
            dq.pop_front();
        }

        // --- 逻辑 2：从队尾维护队列的单调递增性 ---
        // 在将 j 入队前，如果 p[j] <= p[dq.back()]
        while (!dq.empty() && p[j] <= p[dq.back()]) {
            // 关键逻辑：为什么可以 pop_back？
            // 1. p[j] 更小，作为“减数”更容易让后面的 p[j'] - p[j] >= k 成立（更强）。
            // 2. j 下标更大，作为左端点时，区间长度会更短（更年轻）。
            // 既然 j 比 dq.back() 又强又年轻，dq.back() 就可以“退役”了。
            dq.pop_back();
        }

        dq.push_back(j);
    }

    if (ans > n) cout << -1 << endl;
    else cout << ans << endl;
}

int main() {
    // NOI 竞赛必备：极大提升 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度：$O(n)$

• 计算前缀和：遍历一次数组，耗时 $O(n)$。
• 单调队列遍历：
  • 尽管外部有一个 for 循环，内部有两个 while 循环，但观察每一个下标 $j$。
  • 每个下标 $j$ 最多只会被执行一次 push_back（入队）。
  • 一旦入队，它最多只会被执行一次 pop_front 或 pop_back（出队）。
  • 结论：整个过程中对队列的操作总次数是 $O(n)$ 级别的。总时间复杂度为线性 $O(n)$。

2. 空间复杂度：$O(n)$

• 需要 $O(n)$ 存储前缀和数组。
• 单调队列在最坏情况下（如数组递增且不满足 $k$）会存储 $O(n)$ 个下标。
• 结论：总空间复杂度为 $O(n)$。

三、 时间复杂度优化建议 (NOI 提高组技巧)

在 NOI/NOIP 考场上，若 $N$ 达到 $10^6$ 且时限卡得非常死，可以考虑以下优化：

1. 手动模拟双端队列 (Array-based Deque)： std::deque 是分段连续存储，内部存在复杂的指针跳转和内存分配。使用原生数组模拟队列，速度通常能提升 2-4 倍。

   int q[100005]; 
   int head = 0, tail = -1;
   // q[++tail] = j; (push)
   // head++; (pop_front)
   // tail--; (pop_back)
   

2. 避免 endl： endl 会触发强制刷新缓冲区，在输出量大时极慢。请始终使用 '\n'。

3. 前缀和原地计算： 如果内存限制非常苛刻，可以不额外开辟 p 数组，直接在读取 A[i] 的过程中维护当前前缀和及单调队列，但这会增加逻辑复杂度。

四、 教练总结：读题时的思维锚点

这道题在 LeetCode 上被标记为 Hard，难点就在于打破双指针的思维定势。

• 什么时候用双指针？ 当数组元素全为正，前缀和单调增加时，左指针右移必导致和减小。
• 什么时候用单调队列？ 当数组有负数，前缀和不再单调时。我们需要在历史记录中，寻找那些“值极小”且“位置极靠后”的候选起点。

读题关键词总结：

1. “连续子数组” $\rightarrow$ 联想前缀和。
2. “和至少为 K” $\rightarrow$ 转化为 $P[j] - P[i] \ge K$。
3. “最短” $\rightarrow$ 寻找离 $j$ 最近的 $i$。
4. “包含负数” $\rightarrow$ 强制要求对前缀和进行单调性维护。

去尝试在草稿纸上模拟一下 2, -1, 2 这个例子，看看 -1 是如何被更有潜力的后续元素替换掉的。加油！