NC15553 数学考试

NC15553 数学考试

题目地址：

https://ac.nowcoder.com/acm/problem/15553

基本题意

在数组中找两段长度为k的不连续(其实我感觉叫不重和比较好)区间，使得两段区间的和最大。
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。

基本思路：

1. 其实就是确定一个分界，左右分别找长度为k的值最大区间;
2. 为了快速求区间的和，我们可以使用前缀和预处理数组;
3. 然后从前往后每次更新[i - k, i]区间的最大值,同理再从后往前扫每次更新[i + 1,i + k + 1] 区间的最大值(这里是防止重复加i处的值);
4. 最后枚举每个可能分界，然后取最大值为答案就行了;
5. 注意将前后长度不足k的部分跳过。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF 0x3f3f3f3f
inline int read() {
    int x = 0, neg = 1; char op = getchar();
    while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
    while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
    return neg * x;
}
inline void print(int x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x >= 10) print(x / 10);
    putchar(x % 10 + '0');
}
const int maxn = 2e5 + 10;
int n,k,a[maxn],sum[maxn];
int mx_l[maxn],mx_r[maxn];
signed main() {
    IO;
    int t;
    cin >> t;
    while (t-- > 0) {
        cin >> n >> k;
        fill(mx_l+1,mx_l+n+1,-1e18);
        fill(mx_r+1,mx_r+n+1,-1e18);
        rep(i, 1, n) cin >> a[i];
        sum[0] = 0;
        rep(i, 1, n) sum[i] = sum[i - 1] + a[i]; // 预处理前缀和;
        rep(i, k, n) {
            mx_l[i] = max(mx_l[i - 1], sum[i] - sum[i - k]); //i之前长度为k的区间的最大值(包括a[i]);
        }
        per(i, n - k, 1) {
            mx_r[i] = max(mx_r[i + 1], sum[i + k] - sum[i]); //i之后长度为k的区间的最大值(不包括a[i]);
        }
        int ans = -1e18;
        rep(i, k, n-k) {
            ans = max(ans, mx_l[i] + mx_r[i]);
        }
        cout << ans << endl;
    }
    return 0;
}