牛客 数学考试【题解】

链接: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;
}
上一篇:通达信函数详解(转)


下一篇:2020.06.01——习题训练4