dd爱框框
时间限制：2秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
读入n nn，x xx,给出n nn个数a [ 1 ] , a [ 2 ] , … … , a [ n ] a[1],a[2],……,a[n]a[1],a[2],……,a[n],求最小的区间[ l , r ] [l,r][l,r]，使a [ l ] + a [ l + 1 ] + … … + a [ r ] ≥ x a[l]+a[l+1]+……+a[r]≥xa[l]+a[l+1]+……+a[r]≥x，若存在相同长度区间，输出l ll最小的那个
输入描述：
第一行两个数，n ( 1 ≤ n ≤ 10000000 ) , x ( 1 ≤ x ≤ 10000 ) n(1≤n≤10000000),x(1≤x≤10000)n(1≤n≤10000000),x(1≤x≤10000)
第二行n nn个数a [ i ] ( 1 ≤ a [ i ] ≤ 1000 ) a[i](1≤a[i]≤1000)a[i](1≤a[i]≤1000)
输出描述：
输出符合条件l , r l,rl,r(保证有解)
示例1
输入：
10 20 1 1 6 10 9 3 3 5 3 7输出：
3 5解题思路
本题核心是滑动窗口（双指针）+前缀和，求解和不小于指定值的最短连续子区间。由于数组元素均为正数，满足滑动窗口的使用条件：右指针不断向右扩展区间，累加区间和；当区间和≥ x ≥x≥x时，尝试左移左指针缩小窗口，同步更新最短区间的长度与左右端点。若存在长度相同的区间，优先保留左端点更小的方案。前缀和数组实现O ( 1 ) O(1)O(1)区间和查询，整体仅需一次遍历，时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( n ) O(n)O(n)，高效适配n ≤ 10 7 n≤10^7n≤107的超大数据规模，杜绝暴力枚举的超时风险。
总结
核心逻辑：利用正数数组的单调性，滑动窗口线性遍历，找到和≥ x ≥x≥x的最短子区间。
关键操作：前缀和快速计算区间和，双指针动态调整窗口大小，记录最优区间端点。
效率保障：线性时间复杂度，无冗余计算，完美处理千万级数据量的约束。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=5e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;intmain(){ll n,k;cin>>n>>k;vector<ll>a(n+1,0),b(n+1,0);for(ll i=1;i<=n;i++){cin>>a[i];b[i]=b[i-1]+a[i];}ll len=INT_MAX;ll ls=0,rs=0;ll l=1;for(ll r=1;r<=n;r++){while(l<r&&b[r]-b[l-1]>=k){if(b[r]-b[l-1]>=k&&r-l+1<len){len=r-l+1;ls=l,rs=r;}l++;}}cout<<ls<<' '<<rs<<endl;return0;}
