数学考试

活动地址：https://ac.nowcoder.com/discuss/392146?type=101

思路

由于本人很菜，所有贡献一个做法。

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
ll sum[maxn];
struct node{
    ll sum;
    int idx;
    bool operator < (const node & o) const{
        return sum < o.sum;
    }
};
priority_queue<node> q;
int main(){
    cin>>T;
    while(T--){
        while(q.size()) q.pop();
        int n,k;cin>>n>>k;
        ll res = -1e18;
        for(int i = 1;i<=n;i++) {
            scanf("%lld",&sum[i]);
            sum[i] += sum[i-1];
            if(i>=k) q.push({sum[i] - sum[i-k],i});
        }
        for(int i = k;i+k<=n;i++){
            ll cur = sum[i]-sum[i-k];
            while(q.top().idx < i+k) q.pop();
            cur += q.top().sum;
            res = max(res,cur);
        }
        printf("%lld\n",res);
    }

    return 0;
}

更新一个做法

其实这个做法就是记录了一个mx_sum[i],表示i及以后最大的k长度区间和的值，所以这个只需要倒着遍历，不断取最值就行了。然后对于所有的i;
res = max(res,sumk[i] + mx_sum[i+k])
sumk[i]：以i结尾的k长度区间和

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int T;
ll sum[maxn];
ll sumk[maxn],mx_sum[maxn];
int main(){
    cin>>T;
    while(T--){
        int n,k;cin>>n>>k;
        ll res = -1e18;
        for(int i = 1;i<=n;i++) {
            scanf("%lld",&sum[i]);
            sum[i] += sum[i-1];
            if(i>=k) sumk[i] = sum[i] - sum[i-k];
        }
        mx_sum[n] = sumk[n];
        for(int i = n-1;i>=k;i--) mx_sum[i] = max(sumk[i],mx_sum[i+1]);
        for(int i = k;i+k<=n;i++) res = max(res,sumk[i]+mx_sum[i+k]);
        printf("%lld\n",res);
    }
    return 0;
}