题意

题目链接。

给定一个序列，包含 $n$ 个有重量和价值的物品。需要找出一个连续区间，可以选择其中的至多 $w$ 个物品令其重量减半（向上取整）而价值不变，然后该区间重量和须不大于 $k$。求满足这样条件的总价值最大的区间。

解析

求区间最大价值容易想到双指针。考虑如何维护重量减半（以下简称打折）的 $w$ 个物品。

由于元素会有重复，考虑用两个 multiset，一个用来维护打折的物品，另一个用来维护不打折的物品。

当加入一个新物品时，我们先将其加入打折物品中，然后如果打折物品超出了 $w$ 个，取出其中重量最小的令其不打折即可。这样就完成了右指针的右移操作。

当删除一个物品时，我们先将其与打折物品中重量最低的那个进行比较，如果其重量大于等于打折物品最小重量，说明其为打折物品，在打折物品中删除，然后如果有未打折物品的话，将其中重量最大的进行打折即可。如果其重量小于打折物品最小重量，直接在未打折物品中删除即可。

容易发现，在这些过程中我们很容易维护区间重量和以及区间价值和，本题至此解决。一些细节问题见代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,w,k;
int a[N],t[N];
int l,now,happy,ans;
multiset<int> s1,s2;
int main(){
    scanf("%d%d%d",&n,&w,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);
    l=1;
    for(int r=1;r<=n;r++){//双指针
        s1.insert(t[r]);
        now+=(t[r]+1)>>1;happy+=a[r];//加入物品
        if(s1.size()>w){//如果打折物品太多了，转移一个重量最小的
            s2.insert(*s1.begin());
            now+=*s1.begin();
            now-=(*s1.begin()+1)>>1;
            s1.erase(s1.begin());
        }
        while(now>k){//删除操作
            if(t[l]>=*s1.begin()){
                now-=(t[l]+1)>>1;
                s1.erase(s1.find(t[l]));//不能直接 erase(t[l])，因为该操作会把所有等重量的物品都删除，而我们只需要删除一个，因此需要 find() 一下
                if(!s2.empty()){
                    s1.insert(*s2.rbegin());//rbegin() 取反向开头，比 end() 方便
                    now-=*s2.rbegin();
                    now+=(*s2.rbegin()+1)>>1;
                    s2.erase(s2.find(*s2.rbegin()));
                }
            }
            else{
                now-=t[l];
                s2.erase(s2.find(t[l]));
            }
            happy-=a[l];//过程中重量和和价值和小心处理好
            l++;
        }
        ans=max(ans,happy);//更新答案
    }
    printf("%d\n",ans);
    return 0;
}