题目描述

给定 $N$ 个正整数组成的数列 $a_1, a_2, \cdots, a_n$ 和一个整数 $m$。求出这个数列中的一个子区间 $[i, j]$,也就是在这个数列中连续的数字 $a_i, a_{i + 1}, \cdots, a_{j - 1}, a_j$,使得这个子区间的和在不超过 $M$ 的情况下最大。如果有多个区间符合要求,请输出 $i$ 最小的那一个。

输入格式

输入共两行。

第一行,两个整数 $N,M$;

第二行,$N$ 个整数 $a_1, a_2, \cdots, a_n$。

输出格式

一行,三个整数,表示符合题意的区间的左端点、右端点和累加和。

输入输出样例

输入 #1

5 10
2 3 4 5 6

输出 #1

1 3 9

分析

可以很容易的想到从大到小枚举子区间,但无奈复杂度过高,便可以想到利用前缀和来优化,复杂度大约$O(n^2)$,仍然过不了大数据。于是我们重新观察题目,发现两个端点都不是固定的且它们之间有种奇妙的联系,很轻松就可以想到用双指针优化来进一步减少我们的算法复杂度。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[4000001],ans_l,ans_r,ans,l=1,r=1,q[4000001];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        q[i]=q[i-1]+a[i];
    }
    while(r<=n){
        while(q[r]-q[l-1]>m&&l<=r)l++;
        if(q[r]-q[l-1]>ans){
            ans=q[r]-q[l-1];
            ans_l=l,ans_r=r;
        }
        r++;
    }
    printf("%d %d %d",ans_l,ans_r,ans);
    return 0;
}
最后修改:2021 年 02 月 12 日 04 : 44 PM
如果觉得我的文章对你有用,请随意赞赏