边界枚举(双指针)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
//给一个长度为n的数组,取其中的(连续)子序列,要求他们的值大于num。求最小的子序列长度
int main() {
    int m;
    cin >> m;
    int data[100100];//1~x1的序列
    while (m--) {
        int x1, x2;
        cin >> x1 >> x2;
        memset(data,0,sizeof(data));
        //重新覆盖数组的值,避免原有值受到影响
        for (int i = 1; i <=x1 ; i++) {
            cin >> data[i];
        }
        int sum = 0;
        int r = 0;//技巧
        int result = x1 + 1;//技巧
        for (int l = 1; l <= x1; l++) {
            while (r <= x1 && sum < x2) {
                r++;//技巧
                sum += data[r];
            }//sum一直累和直到刚刚好大于num,退出循环

            if (sum >= x2) {
                result = min(r - l + 1, result);//更新子序列长度
            }
            sum-=data[l];
            //此时只是需要l向前移动,r固定(指导l移动后,子序列的累和值小于sum r在开始移动)
        }
        if(result>x1)
            cout<<0<<endl;
        else
            cout<<result<<endl;
    }
    return 0;
}
全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
正在热议
更多
# 春招至今,你的战绩如何? #
10491次浏览 92人参与
# 你的实习产出是真实的还是包装的? #
1855次浏览 42人参与
# MiniMax求职进展汇总 #
24004次浏览 308人参与
# 军工所铁饭碗 vs 互联网高薪资,你会选谁 #
7561次浏览 43人参与
# 简历第一个项目做什么 #
31664次浏览 335人参与
# 重来一次,我还会选择这个专业吗 #
433439次浏览 3926人参与
# 巨人网络春招 #
11324次浏览 223人参与
# 当下环境,你会继续卷互联网,还是看其他行业机会 #
187103次浏览 1122人参与
# 牛客AI文生图 #
21422次浏览 238人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
152348次浏览 888人参与
# 研究所笔面经互助 #
118898次浏览 577人参与
# 简历中的项目经历要怎么写? #
310217次浏览 4210人参与
# AI时代,哪些岗位最容易被淘汰 #
63642次浏览 822人参与
# 面试紧张时你会有什么表现? #
30505次浏览 188人参与
# 你今年的平均薪资是多少? #
213074次浏览 1039人参与
# 你怎么看待AI面试 #
180035次浏览 1255人参与
# 高学历就一定能找到好工作吗? #
64324次浏览 620人参与
# 你最满意的offer薪资是哪家公司? #
76485次浏览 374人参与
# 我的求职精神状态 #
448043次浏览 3129人参与
# 正在春招的你,也参与了去年秋招吗? #
363373次浏览 2638人参与
# 腾讯音乐求职进展汇总 #
160638次浏览 1111人参与
# 校招笔试 #
470875次浏览 2964人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务