链接:https://ac.nowcoder.com/acm/problem/15553
题目
今天qwb要参加一个数学考试,这套试卷一共有n道题,每道题qwb能获得的分数为ai,qwb并不打算把这些题全做完,
他想选总共2k道题来做,并且期望他能获得的分数尽可能的大,他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1],[R,R+1,R+2,...,R+k-1](R >= L+k)。
输入
第一行一个整数T(T<=10),代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an,(-100,000<=ai<=100,000)
输出
输出一个整数,qwb能获得的最大分数
分析
首先预判下该题的时间复杂度。n<=200,000,极限数据下n2会TLE,
可推断出该题时间复杂度至多为nlogn量级。
再看题划重点——选2个不连续的长度为k的区间,
即:“求两个固定长度的最大区间和”,那么很自然想到用前缀和。
首先,我们可以从左往右找到一个长度为k的最大区间和,记作:Ma。
所以,
\[Ma=max\left\{Ma,a[i]-a[i-k]\right\} \]
对于求Ma过程中扫描过的每个a[i],我们都可以找到一个与之对应的区间和a[i+k]-a[i]。
所以要求的两个不连续最大区间和,就等于Ma+a[i+k]-a[i]的最大值,即:
\[ans=max\left\{ans,Ma+a[i+k]-a[i]\right\} \]
这个算法的时间复杂度是O(n),在接受范围之内。
最后需要注意的是,极限数据答案为25×105>231-1,
即:会爆int。所以数组a,第一个区间最大和Ma和最后答案ans,都要开成long long。
代码
#include<iostream>
using namespace std;
const int N=1e6;
typedef long long ll;
ll a[N];
int main(){
int T;
cin>>T;
while(T--){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
ll Ma=-1e10,ans=-1e10;
for(int i=k;i+k<=n;i++){
Ma=max(Ma,a[i]-a[i-k]);
ans=max(ans,Ma+a[i+k]-a[i]);
}
cout<<ans<<endl;
}
return 0;
}