题解 | #E Problem#

问题分析：

有一个包含 n 个方块的序列，每个方块上有一个数字。还有一个额外的万能方块，初始值为 k。

游戏规则：可以把万能方块插入到序列的最左边，同时最右边的方块会被移出序列，变成新的万能方块。可以执行任意多次操作（包括0次）。

目的：找到一个最优的操作次数，使得最终序列最左边的数字加上最终万能方块的数字的和最大。

总共有三种情况：操作0次，操作1次，操作两次及以上

1.如果不动，就是a[0]+k

2.如果动一次，就是a[n-1]+k

3.如果动两次及以上，就是相邻两个数的和

代码实现：

#include<bits/stdc++.h>

using namespace std;

int main() {

int T;
cin >> T;
for(int i=0;i<T;i++)
{
    int n,k;
    cin >> n >> k;
    vector<int>a(n);
    for(int j=0;j<n;j++)
    {
        cin >> a[j];
    }
    int numx=a[0]+k;
    numx=max(numx,a[n-1]+k);
    int num=-20000000;
    for(int j=1;j<n;j++)
    {
        num=max(num,a[j]+a[j-1]);
    }
    numx=max(numx,num);
    cout << numx << '\n';
}
return 0;

}

时间复杂度为O(n)