P5745 【深基附B例】区间最大和
【深基附B例】区间最大和
题目描述
给定 n 个正整数组成的数列 a_1, a_2, ..., a_n 和一个整数 m。求出这个数列中的一个子区间 [i, j]，也就是在这个数列中连续的数字 a_i, a_{i + 1}, ..., a_{j - 1}, a_j，使得这个子区间的和在不超过 m 的情况下最大。如果有多个区间符合要求，请输出 i 最小的那一个。
输入格式
输入共两行。
第一行，两个整数 n, m；
第二行，n 个整数 a_1, a_2, ..., a_n。
输出格式
一行，三个整数，表示符合题意的区间的左端点、右端点和累加和。
样例 #1
样例输入 #1
5 10
2 3 4 5 6
样例输出 #1
1 3 9
提示
子任务 1（10分）：n≤ 200 ；
子任务 2（20分）：n≤ 3000 ；
子任务 3（30分）：n≤ 10^5 ；
子任务 4（40分）：n≤ 4× 10^6 。
对于 100% 的数据，1 ≤ n ≤ 4 × 10^6，1 ≤ m ≤ 10^9，0 ≤ a_1, a_2, ..., a_n ≤ 10^5。
分析
后面修改了树状数组代码的时间复杂度的重要性
这题难度不大，但对于新手来说，不算很友好。所以我们循序渐进，慢慢来刨析这道题目
10分代码：
很容易想到枚举所有的ii到jj,再对ii到jj进行求和，再判断是否满足条件，满足就更新答案。
时间复杂度O(n^3)
代码:
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[4000001];
int ans1,ans2,ans3;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){//读入
scanf("%d",&a[i]);
}
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){//枚举i与j
int sum=0;
for(int k=i; k<=j; k++){//求和
sum+=a[k];
}
if(sum>ans3&&sum<=m){//如果这个答案比以前的更优，则更新答案
ans1=i;
ans2=j;
ans3=sum;
}
}
}
cout<<ans1<<" "<<ans2<<" "<<ans3;//输出
}
30分代码：
因为要对区间进行求和，自然就会想到前缀和来维护。
我们记sum_i=a_1+a_2+......+a_i
则a_l+a_{l+1}+......a_r=sum_r-sum_l-1
在读入的过程中预处理前缀和
时间复杂度：O(n^2)
代码:
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[4000001];
int sum[4000001];//用sum数组来记录前缀和
int ans1,ans2,ans3;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];//处理前缀和
}
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
int cnt=sum[j]-sum[i-1];
if(cnt>ans3&&cnt<=m){//计算前缀和并更新答案
ans1=i;
ans2=j;
ans3=cnt;
}
}
}
cout<<ans1<<" "<<ans2<<" "<<ans3;
}
60分代码:
因为所有的a_i都是正整数，故sum单调递增。
所以若的sum_r-sum_{l-1}>m,
因为sum_{r+1}>sum_{r}
故sum_{r+1}-sum_{l-1}>m
后面的sum_{r+k}-sum_{l-1}>m
所以就可以break了
时间复杂度:O(n^2)+小常数
代码：
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[4000001];
int sum[4000001];
int ans1,ans2,ans3;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j++){
int cnt=sum[j]-sum[i-1];
if(cnt>ans3&&cnt<=m){
ans1=i;
ans2=j;
ans3=cnt;
}
if(cnt>m) break;//如果比m大就可以退出了，不必要继续枚举了
}
}
cout<<ans1<<" "<<ans2<<" "<<ans3;
}
100分代码:
因为sum单调递增。
所以考虑枚举i，再二分确定j
时间复杂度:O(nlogn)
代码:
#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
long long sum[4000001];
long long n,m;
long long a[4000001];
int ans1,ans2,ans3;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){//预处理前缀和
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=1; i<=n; i++){
int l=i,r=n;
while(l<=r){//二分确定最优的j
int mid=(l+r)/2;
if(sum[mid]-sum[i-1]>m){
r=mid-1;
} else {
l=mid+1;
}
}
if(sum[r]-sum[i-1]<=m){//对于当前的i来说，这个j已经是最优的了，所以更新答案
if(sum[r]-sum[i-1]>ans3){
ans1=i;
ans2=r;
ans3=sum[r]-sum[i-1];
}
}
}
cout<<ans1<<' '<<ans2<<' '<<ans3;
return 0;
}
O(n)的做法:
给出的做法是：
维护一个队列，让数组中的数依次入队，并记录其的元素和，若大于m,则让对首出列，更新答案，再让后面的数字继续入队，并更新答案，不断的这么操作，直到所有数字都入过队了为止。
我这里采用了STL的deque(双端队列),感兴趣的Oler们可以去了解一下
代码:
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[4000001];
deque<int>q;
int sum=0;
int ans1,ans2,ans3;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
}
int l=1;
for(int i=1; i<=n; i++){
q.push_back(a[i]);//插入a[i]
sum+=a[i];
while(sum>m){//如果队列中的值大于m,则对队列进行维护
q.pop_front();//弹去队首
sum-=a[i];//更新答案
if(sum>ans3){
ans3=sum;
ans2=i-1;
ans1=l;
}
sum+=a[i];//维护队列中的元素的和
sum-=a[l];
l++;
}
}
cout<<ans1<<" "<<ans2<<" "<<ans3;
}
O(nlog^2n)的做法
还有一种做法是使用树状数组。
我们知道树状数组也能对区间进行求和，所以可以使用在之前二分的代码加上树状数组
不会树状数组也没关系，你可以去洛谷找到树状数组的模板题，对其进行学习。
代码:
#include <bits/stdc++.h>
//#include <windows.h>
using namespace std;
int c[8000001];
int n,m;
int a[4000001];
int lowbit(int n){//树状数组的核心函数
return n&(-n);
}
int add(int x,int y){//单点修改
for(;x<=n; x+=lowbit(x)) c[x]+=y;
}
int sum(int x){//区间求和
int ans=0;
for(;x;x-=lowbit(x)) ans+=c[x];
return ans;
}
int ans1,ans2,ans3;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
add(i,a[i]);
}
for(int i=1; i<=n; i++){//二分的步骤
int l=i,r=n;
while(l<=r){
int mid=(l+r)/2;
if(sum(mid)-sum(i-1)>m){
r=mid-1;
} else {
l=mid+1;
}
}
int cnt=sum(r)-sum(i-1);
if(cnt<=m){
if(cnt>ans3){
ans1=i;
ans2=r;
ans3=cnt;
}
}
}
cout<<ans1<<' '<<ans2<<' '<<ans3;
return 0;
}