原题链接

题目大意

t组数据，每组数据给出长为n的数组，每个元素ai代表一个点，元素大小代表此位置上的蘑菇数量，0时刻可以选择任意初始位置（此时不收集此点上的蘑菇），此新每一分钟下列事件顺序发生：

1.向左或向右移动一个位置（也可以不动）

2.收集当前点上的所有蘑菇

3.每个点上出现一个新蘑菇

要求程序求出k分钟新能够收集的最大磨菇数

数据范围：(1≤t≤1e4) (1≤n≤2e5, 1≤k≤1e9) (1≤ai≤1e9)

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
intput

4
5 2
5 6 1 2 3
5 7
5 6 1 2 3
1 2
999999
5 70000
1000000000 1000000000 1000000000 1000000000 1000000000

output

12
37
1000000
5000349985

题解

此题codeforces难度为1600，代码虽然简单，但是思维量较大，容易将问题想复杂，需要在心里模拟过程发现规律并分解问题，这份题解只用于记录简要思路和过程，只能提供“想法是什么”，不能提供“怎么能产生这样的想法”以及“为什么这样想是正确的”。建议先独立想出思路再看题解，否则没有锻炼思维能力的效果

把新增加的蘑菇和初始的蘑菇分为两部分来看会更清楚一些，初始的好说，需要想一想怎么才能收集最多新出现的蘑菇

需要分类讨论：

  1. k小于n时，找到初始最大区间并求和，加上在这个区间内能收集的最多新出现的磨菇数（最多数量可以证明为等差数列求和，项数为(k-1)，首项为1，末项为(k-1)），随后两部分相加即为答案

  2. k≥n时，必定能收集全部初始蘑菇，这里新出现的蘑菇的收集思考方式比较独特，剩余时间为(k-n)以前新出现的蘑菇要么等效于要么就是能够全部收集，之后设当前时间为，单独考虑每次所有点蘑菇加一，这些蘑菇要么等效于要么就是最多只能采i个，剩下(n-i)个，以此类推总共剩下的磨菇数就是，进而采集到的新出现的最大数量为，两部分相加即可

使用前缀和快速求出区间和，数据量较大，记得开long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int t,n,k;
LL g[N];

int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&g[i]);
            g[i]+=g[i-1];
        }
        LL ans=0;
        if(k>=n){
            ans=g[n];
            ans+=((k-1ll+k-n)*n/2);
            printf("%lld\n",ans);
        }
        else{
            LL mx=g[k];
            for(int i=k+1;i<=n;i++) mx=max(mx,g[i]-g[i-k]);
            mx+=(k*(k-1ll)/2);
            printf("%lld\n",mx);
        }
    }
    return 0;
}