【题解】数列求和
题解 求和 数列
2023-06-13 09:13:01 时间
题目描述
给定 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 年 07 月 20 日 03 : 06 PM
© 允许规范转载