题目

题目描述:
今天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能获得的最大分数


解析

这道题说要求区间和,我们自然而然就能想到前缀和
这道题我一开始想到先求最大区间,再在两边求次大区间,但是硬核66.7%(其实我知道是错的,但是不知道原因)
for (int i = 0, j = k; j <= n; i++, j++)
    if (ans1 < sum[j] - sum[i]) {
        ans1 = sum[j] - sum[i];
        l = i, r = j;
    }
int ans2 = -INF;
for (int i = 0, j = k; j <= l; i++, j++)
    ans2 = max(ans2, sum[j] - sum[i]);
for (int i = r, j = r + k; j <= n; i++, j++)
    ans2 = max(ans2, sum[j] - sum[i]);
printf("%d\n", ans1 + ans2);

所以呢,在前缀和的基础上,我们还是要求两个区间。
算法讲解:
  1. 首先,这道题,我们的区间是定长的,为k。
  2. 然后我们要求两个区间:所以区间肯定!一个左一个右。(废话)
  3. 但是我们这样就能想到,我们确定一个点,然后对左右区间求极值不就好了
    ll lans = -INF, rans = -INF;
    for (int i = k; i + k <= n; i++) {
        lans = max(lans, sum[i] - sum[i - k]);
        rans = max(rans, sum[i + k] - sum[i]);
    }
  4. 但是这样肯定是不对的!因为左右区间可能重合。那怎么样才是对的呢?
  5. 我们既然这样有可能重合,所以我们就要让他不能重合,所以只求左边的极值。右边就在左边的基础上求极值就行了。
    ll lans = -INF, ans = -INF;
    for (int i = k; i + k <= n; i++) {
        lans = max(lans, sum[i] - sum[i - k]);
        ans = max(ans, lans + sum[i + k] - sum[i]);
    }
    
    比如这样~

打代码:
  1. 存数据
  2. 找区间
  3. 出答案
  4. 484很有道理!看代码吧~


AC代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
//代码预处理区

const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 2e6 + 7;
ll sum[MAX];
//全局变量区

template<class T>inline void read(T& res);
//函数预定义区

int main() {
    int T; read(T);
    while (T--) {
        int n, k; read(n); read(k);
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            read(sum[i]); sum[i] += sum[i - 1];
        }
        ll lans = -INF, ans = -INF;
        for (int i = k; i + k <= n; i++) {
            lans = max(lans, sum[i] - sum[i - k]);
            ans = max(ans, lans + sum[i + k] - sum[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
//函数区