【每日一题】数学考试题解

链接：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能获得的最大分数
示例1
输入
2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1
输出
6
7

Solution

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll mod = 998244353;
const int DEG = 30;
const double pi = acos(-1.0);
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll a[N];
ll pre[N], last[N]; // 前缀和 与 后缀和
ll l[N], r[N]; // 前面最大的连续和 与 后面最大的连续和
int n, k;
int main(){
  int t;
  cin >> t;
  while(t--){
    cin >> n >> k;
    pre[0] = last[n + 1] = 0;  // 多组数据一定要小心处理前面test留下的数据
    l[0] = -1e18, r[n + 1] = -1e18; // 同上
    for(int i = 1; i <= n; i++) cin >> a[i], pre[i] = pre[i - 1] + a[i]; // 处理前缀和
    for(int i = n; i >= 1; i--) last[i] = last[i + 1] + a[i]; // 处理后缀和
    for(int i = 1; i <= n; i++){
      if(i < k){
        l[i] = -1e18;   // 如果 i < k 证明取不了长度为 k 的连续和
      }
      else l[i] = max(l[i - 1], pre[i] - pre[i - k]); // l[i] 表示包含 i 点的 i 之前所有长度为 k 的连续和的最大值
    }
    for(int i = n; i >= 1; i--){
      if(i > n - k + 1){
        r[i] = -1e18; // i > n - k + 1 证明后面取不了长度为 k 的连续和
      }
      else r[i] = max(r[i + 1], last[i] - last[i + k]); // r[i] 表示包含 i 点的 i 之后所有长度为 k 的连续和的最大值
    }
    ll ans = -1e18;
    for(int i = k; i <= n; i++){
      ans = max(ans, l[i] + r[i + 1]);// 取一个点 求前面最大的长度为 k 连续和与它后面长度为 k 的连续和
    }
    cout << ans << "\n";
  }
  return 0;
}