小苯的能量项链
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
小苯有一个含有
n
n
n 颗珠子的“能量项链”，珠子排成一排，其中第
i
i
i 颗珠子的能量为
a
i
a_i
ai。
但是这个项链并不稳定，如果项链的珠子个数不少于 3 个，则它即将发生“崩坏”，即：除了第一颗珠子和最后一颗珠子以外的其余所有珠子都将销毁，最终只留下第一颗和最后一颗珠子。
小苯现在希望项链在“崩坏”后保留尽可能多的能量，为此他可以在崩坏前执行以下的操作：
- 去掉项链的第一颗珠子（也就意味着项链原本的第二颗珠子将会变成第一颗）。
- 去掉项链的最后一颗珠子（也就意味着项链原本的倒数第二颗珠子将会变成最后一颗）。
两种操作各自均需要花费 1 秒时间，而现在距离项链发生“崩坏”仅剩
k
k
k 秒，小苯想知道，他最多可以保留住多少能量，请你帮他算一算吧。
输入描述
每个测试文件内都包含多组测试数据。
第一行一个正整数
T
(
1
≤
T
≤
1000
)
T\\ (1 \\le T \\le 1000)
T (1≤T≤1000)，表示测试数据的组数。
接下来对于每组测试数据，输入包含两行。
第一行两个整数
n
,
k
(
1
≤
n
≤
5
×
10
5
,
0
≤
k
≤
10
9
)
n,k\\ (1 \\le n \\le 5 \\times 10^5,0 \\le k \\le 10^9)
n,k (1≤n≤5×105,0≤k≤109)，表示项链的珠子个数和距离项链“崩坏”的时间。
第二行
n
n
n 个正整数
a
i
(
1
≤
a
i
≤
10
9
)
a_i\\ (1 \\le a_i \\le 10^9)
ai (1≤ai≤109)，表示每颗珠子的能量。
（保证所有测试数据中
n
n
n 的总和不超过
5
×
10
5
5 \\times 10^5
5×105。）
输出描述
对于每组测试数据，输出一行一个整数表示小苯能保留的最大能量。
示例1
输入：
2
5 2
2 3 4 5 2
1 1
114514
输出：
8
114514
说明： 对于第一组测试数据，距离发生“崩坏”还有
k
=
2
k=2
k=2 秒，最优的方案是删除目前的第一个和最后一个数字，那么项链的能量会变成
{
3
,
4
,
5
}
\\{3,4,5\\}
{3,4,5}，最终
3
3
3 和
5
5
5 会保留下来，因此最大值为
8
8
8。
对于第二组测试数据，由于项链珠子个数小于3，因此不会发生崩坏，最终保留的能量就是
114514
114514
114514。
解题思路
本题是贪心 + 滑动窗口维护前缀最大值的经典题型。需要在最多
k
k
k 次删除头/尾操作后，使得最终（可能崩坏后）保留的能量最大。由于崩坏只保留首尾两个珠子（若剩余珠子数
≥
3
\\ge 3
≥3），或者剩余珠子数
<
3
<3
<3 时直接保留全部，问题可以转化为选择两个位置
l
≤
r
l \\le r
l≤r 作为最终保留的首尾，满足操作次数限制，并最大化
v
l
+
v
r
v_l + v_r
vl+vr。
1. 问题等价转化
- 若初始珠子数
n
<
3
n < 3
n<3，不会崩坏，答案就是所有珠子能量之和。 - 若
n
≥
3
n \\ge 3
n≥3，我们通过若干次删除头部和尾部的操作，将原序列缩短为一个新的序列。新序列的首尾珠子在原序列中的下标为l
l
l 和r
r
r，且满足：- 删除操作次数为
(
l
−
1
)
+
(
n
−
r
)
≤
k
(l-1) + (n-r) \\le k
(l−1)+(n−r)≤k； - 最终序列长度为
r
−
l
+
1
r-l+1
r−l+1，可能≥
3
\\ge 3
≥3（发生崩坏，保留v
l
+
v
r
v_l+v_r
vl+vr），也可能=
2
=2
=2（不崩坏，同样保留v
l
+
v
r
v_l+v_r
vl+vr）。无论哪种情况，我们关心的都是v
l
+
v
r
v_l+v_r
vl+vr。
- 删除操作次数为
- 目标：在满足
(
l
−
1
)
+
(
n
−
r
)
≤
k
(l-1)+(n-r) \\le k
(l−1)+(n−r)≤k 且l
<
r
l < r
l<r 的条件下，最大化v
l
+
v
r
v_l + v_r
vl+vr。
2. 算法设计
- 设
d
i
f
=
max
(
2
,
n
−
k
)
dif = \\max(2,\\ n-k)
dif=max(2, n−k)。直观上，最多删除k
k
k 个珠子后，剩余珠子数至少为n
−
k
n-k
n−k；但若n
−
k
≤
2
n-k \\le 2
n−k≤2，则我们至少可以留下2
2
2 个珠子（避免崩坏），所以d
i
f
dif
dif 取2
2
2 保证至少两个珠子。 - 对于固定的右端点
r
r
r，允许的左端点l
l
l 必须满足：(
l
−
1
)
+
(
n
−
r
)
≤
k
⇒
l
≤
r
−
d
i
f
+
1
(l-1)+(n-r) \\le k \\quad\\Rightarrow\\quad l \\le r – dif + 1
(l−1)+(n−r)≤k⇒l≤r−dif+1 其中d
i
f
=
max
(
2
,
n
−
k
)
dif = \\max(2,\\ n-k)
dif=max(2, n−k)。 - 因此，对于每个
r
r
r 从d
i
f
dif
dif 到n
n
n，合法的l
l
l 取值范围是[
1
,
r
−
d
i
f
+
1
]
[1,\\ r-dif+1]
[1, r−dif+1]。我们需要在该前缀中找到最大的v
l
v_l
vl，然后计算v
r
+
max
1
≤
l
≤
r
−
d
i
f
+
1
v
l
v_r + \\max_{1\\le l\\le r-dif+1} v_l
vr+max1≤l≤r−dif+1vl 更新答案。 - 实现时，维护一个变量 mx 表示当前前缀
1
1
1 到i
−
d
i
f
+
1
i-dif+1
i−dif+1 的最大值。随着r
r
r 右移，前缀右端点也在右移，可以动态更新 mx。
3. 复杂度分析
- 时间复杂度：每组数据只需线性扫描一遍数组，
O
(
n
)
O(n)
O(n)。所有测试数据的n
n
n 之和不超过5
×
10
5
5\\times 10^5
5×105，总时间可行。 - 空间复杂度：仅需存储数组和几个变量，
O
(
n
)
O(n)
O(n)。
总结
将操作后的首尾保留问题转化为选择满足约束的两个位置，通过固定右端点并维护左侧前缀最大值，在线性时间内求出最大能量和。dif 的设置巧妙涵盖了剩余珠子数为
2
2
2（不崩坏）和
≥
3
\\ge 3
≥3（崩坏）两种情况，使算法统一简洁。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e3+10;
const ll INF=1e18;
const ll M=1e6+10;
const ll mod=998244353;
using i128=__int128_t;
void solve()
{
ll n,k;
cin>>n>>k;
vector<ll> v(n+1);
for(ll i=1;i<=n;i++) cin>>v[i];
if(n<3)
{
ll ans=0;
for(ll i=1;i<=n;i++) ans+=v[i];
cout<<ans<<'\\n';
return;
}
ll dif=max(2LL,n–k);
ll mx=0;
ll ans=0;
for(ll i=dif;i<=n;i++)
{
mx=max(mx,v[i–dif+1]);
ans=max(ans,mx+v[i]);
}
cout<<ans<<'\\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ll t;
cin>>t;
while(t—) solve();
return 0;
}
