NC221681 dd 爱框框：滑动窗口算法实战

题目描述

算法原理

这道题的核心在于利用滑动窗口来高效地寻找满足条件的子数组。我们不需要枚举所有可能的区间，而是通过两个指针动态维护一个窗口。

初始化时，定义左右指针 prev 和 cur 均指向数组起始位置，同时用一个变量 sum 记录当前窗口内的元素总和。逻辑主要分为两种情况：

当 sum 小于目标值 x 时，说明当前窗口还不够大，需要扩大右边界，即 cur 向右移动，并将新加入的元素累加到 sum 中。

一旦 sum 达到或超过 x，我们就找到了一个可行解。此时需要保存当前的左右边界信息。为了寻找更优解（通常是最短或特定条件下的区间），我们在满足条件的前提下，尝试收缩左边界：减去 arr[prev] 的值，并将 prev 右移。只要收缩后 sum 依然满足条件，就继续记录并收缩，直到不满足为止。

重复上述过程，直到右指针遍历完整个数组。

代码实现

下面是完整的 C++ 实现，注意处理输入输出格式以及索引转换（题目通常要求 1-based 索引）。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 读取输入规模 n 和目标值 x
    int n, x;
    cin >> n >> x;

    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 用于保存最终结果的索引对 [start, end]
    int index[2] = {0};

    // 滑动窗口初始化
    int cur = 0;
    int prev = 0;
    int sum = 0;

    while (cur < n) {
        // 扩展右边界，将当前元素加入窗口
        sum += arr[cur];

        // 当窗口和满足条件时，尝试收缩左边界
        while (sum >= x) {
            // 如果是第一次找到有效窗口，直接记录
            if (index[0] == 0 && index[1] == 0) {
                index[0] = prev;
                index[1] = cur;
                sum -= arr[prev++];
                continue;
            }

            // 比较当前窗口长度与已记录窗口的长度
            int length = index[1] - index[0];
            int camplen = cur - prev;

            // 如果当前窗口更短或长度相等但起始位置更前，则更新结果
            if (length == camplen || length > camplen) {
                if (prev < index[0] || length > camplen) {
                    index[0] = prev;
                    index[1] = cur;
                }
            }

            // 收缩左边界
            sum -= arr[prev++];
        }
        // 右指针继续右移
        cur++;
    }

    // 输出结果，转换为 1-based 索引
    cout << index[0] + 1 << ' ' << index[1] + 1 << endl;
    return 0;
}