原题链接
考察:思维
思路:
??比较明显的是要用单调队列,在一段区间内,可以挑选一些数字变化符号.我们求的最大和只有两方式:尽量将负数变正数,尽量将正数变负数.
??在枚举一段\(len\)区间,求最小的\(k\)个负数的绝对值和,然后剩下的数相加.每移动一位,和要做相应变化.所以需要记录左端点属于绝对值还是普通加减.这里利用\(muliset\)存储.
Code
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,len,nums[N],k;
LL ans = -1e14;
void solve()
{
multiset<int> a,b;
LL sum = 0,res = -1e14;
for(int i=1,j=1;i<=n;i++)
{
if(nums[i]>0)
{
b.insert(nums[i]);
sum+=nums[i];
}else{
if(a.size()+1<=k) sum+=abs(nums[i]),a.insert(nums[i]);
else{
if(a.size()&&nums[i]<*(--a.end()))
{
int x = *(--a.end());
sum-=abs(x);
sum+=x;
b.insert(x);
a.erase(a.find(x));
sum+=abs(nums[i]);
a.insert(nums[i]);
}else sum+=nums[i],b.insert(nums[i]);
}
}
if(i-j+1==len) res = max(res,sum);
if(i-j+2>len)
{
if(b.count(nums[j]))
{
sum-=nums[j];
b.erase(b.find(nums[j]));
}else{
sum-=abs(nums[j]);
a.erase(a.find(nums[j]));
if(*(b.begin())<0&&a.size()+1<=k)
{
int x = *(b.begin());
sum-=(LL)x;//多加了b实在的x
sum+=(LL)abs(x);
a.insert(x);
b.erase(b.begin());
}
}
j++;
}
}
ans = max(res,ans);
}
int main()
{
scanf("%d%d",&n,&len);
for(int i=1;i<=n;i++) scanf("%d",&nums[i]);
scanf("%d",&k);
solve();
for(int i=1;i<=n;i++) nums[i] = -nums[i];
solve();
printf("%lld\n",ans);
return 0;
}