dd爱框框【牛客tracker 每日一题】

dd爱框框时间限制2秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述读入n nnx 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[l1]……a[r]≥xa[l]a[l1]……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的最短子区间。关键操作前缀和快速计算区间和双指针动态调整窗口大小记录最优区间端点。效率保障线性时间复杂度无冗余计算完美处理千万级数据量的约束。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N5e310;constll p1e97;constll INF1e18;constll M1e610;intmain(){ll n,k;cinnk;vectorlla(n1,0),b(n1,0);for(ll i1;in;i){cina[i];b[i]b[i-1]a[i];}ll lenINT_MAX;ll ls0,rs0;ll l1;for(ll r1;rn;r){while(lrb[r]-b[l-1]k){if(b[r]-b[l-1]kr-l1len){lenr-l1;lsl,rsr;}l;}}coutls rsendl;return0;}