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