NC15553 数学考试，对理解前缀和与枚举很有好处。 题目链接：NC15553 数学考试——牛客网
题目描述
今天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）。
输入描述:
1
2
3
| 第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）
|
输出描述:
示例:
输入
1
2
3
4
5
| 2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1
|
输出
分析
首先需要解决的是如何确定一个区间。一个区间显然可以用[左端点, 右端点]这样的数对来确定，而本题中区间的长度是给定的，因此只要用左端点与右端点中的一个点就能确定一个区间，这里我们选用左端点。
然后考虑暴力解法，这题如果用暴力来做，需要O(n2)的复杂度遍历每种可能的区间组合。以及O(k)的复杂度计算每个区间的和。则总的时间复杂度为O(kn2)，最坏情况下kn^2 = 4 x 10^15，显然无法在可接受的时间内完成运算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| //main
//暴力枚举区间组合，求解最大值
for(i : n - k)
{
for(j = i + k : n - k)
{
//Sum为求和函数
maxCount = max(maxCount, Sum(i) + Sum(j))
}
}
//Sum(i)
{
count = 0
for(i : i + k)
{
count += a[i]
}
return count
}
|
看见区间的和可以想到前缀和，通过维护一个前缀和来将每个区间的和的计算时间复杂度降为O(1)，这样整个问题的时间复杂度就降为了枚举的O(n2)，最坏情况下n2 = 4 x 10^10，仍然无法在可接受的时间内完成运算。
1
2
3
4
5
6
7
8
9
10
| //main
//暴力枚举区间组合，求解最大值
for(i : n - k)
{
for(j = i + k : n - k)
{
//sum为维护的区间和
maxCount = max(maxCount, sum[i] + sum[j]
}
}
|
我们规定j一定大于i，由此观察遍历过程
image-20201011145807948
两次遍历中有很多重合部分，对于寻找最大值而言是没有必要的。因为若前进一步后的i' < i，则它们分别加上同一个数后大小关系不变。而变化后i仍在有效取值范围内，因此，维护一个maxi的值即可省略对灰色部分的遍历。
image-20201011151108260
对于j'以后的值无需判断，因为max'定不小于max且j'后的值max和max'都可取用，所以不可能存在max + jx > max' + jx（jx在j'之后）。
image-20201011152355021
因此我们仅需考虑这一部分，其中对于step2，max' + j'即是这一步的最大值，将其与上一步的最大值比较来更新maxCount，再将step2看做step1对其进行相同操作，最后即可求出maxCount的值。
1
2
3
4
5
6
7
| maxi = sum[0];
maxCount = maxi + sum[k];
for(i : n - k)
{
maxi = max(maxi, sum[i]);
maxCount = max(maxCount, maxi + sum[i + k]);
}
|
时间复杂度O(n)，满足题目要求。
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll infinity = 3e10;
int main()
{
ll t;
cin >> t;
while(t--)
{
ll n, k;
cin >> n >> k;
vector<ll> sum(n, 0);
cin >> sum[0];
for(ll i = 1; i < n; ++i)
{
cin >> sum[i];
sum[i] += sum[i - 1];
}
vector<ll> kSum(n + 1 - k, 0);
kSum[0] = sum[k - 1];
for(ll i = 1; i < n + 1 - k; ++i)
{
kSum[i] = sum[i - 1 + k] - sum[i - 1];
}
ll curMax = infinity * -1;
ll count = infinity * -1;
for(ll i = 0; i <= n - 2 * k; ++i)
{
curMax = max(curMax, kSum[i]);
count = max(count, curMax + kSum[i + k]);
}
cout << count << endl;
}
return 0;
}
|