【每日一题】数学考试

数学考试

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能获得的最大分数

解析

这道题说要求区间和，我们自然而然就能想到前缀和。

这道题我一开始想到先求最大区间，再在两边求次大区间，但是硬核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);

所以呢，在前缀和的基础上，我们还是要求两个区间。

算法讲解：

首先，这道题，我们的区间是定长的，为k。
然后我们要求两个区间：所以区间肯定！一个左一个右。（废话）

但是我们这样就能想到，我们确定一个点，然后对左右区间求极值不就好了？

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]);
}

但是这样肯定是不对的！因为左右区间可能重合。那怎么样才是对的呢？

我们既然这样有可能重合，所以我们就要让他不能重合，所以只求左边的极值。右边就在左边的基础上求极值就行了。

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]);
}

比如这样~

打代码：

存数据
找区间
出答案
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;
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏