我要招人

去企业版

首页 > 试题广场 >

dd爱框框

[编程题]dd爱框框

热度指数：991 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

读入 $n，x$ ,给出 $n$ 个数 $a[1],a[2],……,a[n]$ ,求最小的区间 $[l,r]$ ，使 $a[l]+a[l+1]+……+a[r]≥x$ ，若存在相同长度区间，输出 $l$ 最小的那个

输入描述:

第一行两个数，n(1≤n≤10000000),x(1≤x≤10000)
第二行n个数a[i](1≤a[i]≤1000)

输出描述:

输出符合条件l,r(保证有解)

示例1

输入

10 20
1 1 6 10 9 3 3 5 3 7

输出

3 5

备注:

算法知识视频讲解

Java

牛客203596504号

Java代码首次超过所有C++的速度(截至目前)！

本题非常简单，考察的前缀和和滑动窗口。

滑动窗口：看标题就知道这题的重点就在“框框”。

想象下我们用一个框框把数组中一些数字框起来，框里数字累加就是区间和
把框框从左向右滑动，右边进来一个数，左边就出去一个数，就是滑动窗口
滑动过程中，如果缩小框框仍能满足区间和，那就缩小它，最终得到最小区间

前缀和：对于区间和，暴力累加显然太慢了，要想办法更快。
如果对于一个下标，我们有从开头累加到它的和，那就叫前缀和
有了前缀和，直接把左右端点的前缀和相减就能快速得到区间和了
总结：
1. 创建前缀和数组
2. 找到第1个符合条件的区间(框框)
3. 从左往右滑动窗口，边滑动边收缩
时间复杂度：O(n)+O(x)+O(n)=O(n)，没有更快的了，可以常数优化一下。

代码如下：

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int x = in.nextInt();
    // 1. 创建前缀和数组
    long[] prefix = new long[n + 1];
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + in.nextInt();
    }
    // 2. 找到第1个符合条件的区间
    int left = 1;
    int right = 1;
    for (int i = 1; i <= x; i++) {
        if (prefix[i] >= x) {
            right = i;
            break;
        }
    }
    // 3. 从左往右滑动窗口
    for (int l = left + 1, r = right; r <= n; l++, r++) {
        if (prefix[r] - prefix[l - 1] >= x) { // 缩小窗口
            while (l <= r && prefix[r] - prefix[l - 1] >= x) {
                l++;
            }
            left = l - 1;
            right = r;
        }
    }
    System.out.print(left + " " + right + "\n");
}

发表于 2026-04-21 05:25:53 回复(0)

C++

WasserSingen

//简单的我片不要，做的就是复杂的方法！
#include <bits/stdc++.h>
using namespace std;
using piii = pair<int, pair<int, int>>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, x;
    cin >> n >> x;
    vector<int>a(n + 1);
    vector<piii>ans;
    int sum = 0, ji = 1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        if (sum >= x) {
            while (sum >= x) {
                sum -= a[ji];
                ji += 1;
                ans.push_back({sum, {ji-1, i}});
            }
        }
    }
    sort(ans.begin(), ans.end(), [](piii a, piii b) {
        if ((a.second.second - a.second.first) != (b.second.second - b.second.first))
            return (a.second.second - a.second.first) < (b.second.second - b.second.first);
        else return a.second.first < b.second.first;
    });
    //cout << ans[0].first << "\n";
    cout << ans[0].second.first << " " << ans[0].second.second;
}

发表于 2026-04-21 00:41:11 回复(0)

提交观点

问题信息

难度：

2条回答 3收藏 68浏览

dd爱框框

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题