【每日一题】数学考试

思路：先求得一个东西：sum[i]表示从区间[ai...ai+k-1]的区间和，求到n-k+1就OK了，后面的没用；然后呢，搞一个结构体，这个结构体有id和val：分别对应就是i和sum[i]；这个结构体按val排序；然后就可以干坏事了。。。。
先枚举左区间的开头，从1到n-2k+1，对于每一个左区间可用的右区间开头都至少要大于或等于i+k；然后因为按val排好了序，所以取的肯定是最大的区间值，判断最大的这个右区间是否可用，不可用就可以把他扔掉了，因为对于i都是不可用的，那么i+1，i+2...更加是不可用的，然后枚举完左区间开头不断更新最大值自然得到答案；

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5+10;
typedef long long ll;
const ll inf = 1e18;
ll a[N],sum[N];//sum[i]表示以[i,i+k-1]的区间和,i最大n-k+1
int n,k;
struct Node{
    int id;
    ll val;
}P;
bool cmp(Node x,Node y){
    if(x.val != y.val) return x.val > y.val;
    else return x.id < y.id;
}
vector<Node> A;
int main(){
    int t;scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        sum[1] = 0;A.clear();
        for(int i = 1;i <= n;i++) scanf("%lld",a+i);
        for(int i = 1;i <= k;i++) sum[1]+=a[i];
        for(int i = 2;i <= n-k+1;i++){
            sum[i] = sum[i-1] - a[i-1] + a[i+k-1];
        }
        int cnt = 0;
        for(int i = k+1;i <= n-k+1;i++){
            P.id = i;P.val = sum[i];
            A.push_back(P);
        }
        sort(A.begin(),A.end(),cmp);
        int idx = 0;
        ll ans = -inf; 
        for(int i = 1;;i++){
            if(i+2*k-1 > n) break;
            while(A[idx].id < i+k) idx++;
            if(ans < sum[i]+A[idx].val){
                ans = sum[i]+A[idx].val;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}