Problem
题目大意：
有 (k) 的时间，(n) 首歌，听每首歌的时间不一定相同，要求按顺序听一段连续的歌，其中有 (w) 首可以只听一半（向上取整）。每首歌有一个快乐值，听第 (i) 首歌即可获得 (a_i) 的快乐值（不论听整首还是半首），问能获得的最大的快乐值是多少。
Solution
首先有一个很明显的事，就是对于每一个确定的区间左边界 (l)，一定要使 (r) 尽可能的大，也就是确定做断电后，只要能扩展区间就扩展区间。然后看数据范围，(1le n le 2 imes 10^5)，可以想到要用 (O(nlog n)) 或者 (O(n)) 的算法。
于是我们考虑用 two-pointers 解决这题。
这时还需要用到一个贪心，就是对于目前 two-pointers 找到的一个区间 ([l,r])，我们必然让时间最大的 (w) 首歌只听一半。
具体实现时，我们可以用 STL 中的 multiset<> 来存储歌曲，这里不能用 set<> 是因为两首歌的时间可能一样。
我们用两个 multiset<> (s_1,s_2) 分别存储听一半的歌的原本的时间和听整首歌的时间。
对于每次将要进入区间的一个数，我们进行分类讨论：
- 若只有不到 (w) 首歌在 (s1) 中且剩余时间足够听半首歌，弹入 (s_1)。
- 否则，若 (s_1) 中原时间最小的数比当前数要小，则把当前数放入 (s_1)，将那个数放入 (s_2)。(s_1) 存原时间的好处就在这里，如果存半首的时间，将无法确定原时间，把元素放入 (s_2) 时就会出问题。另外，这里还要判一下放进去调整后的时间够不够用。
- 否则，若剩余时间够听整首歌，则把当前数放入 (s_2)。
- 否则，说明这个区间已经最大了，放不进去了，就需要弹出左端点。这里也需要分类讨论：
- 若 (s_2) 为空，左端点一定在 (s_1) 中，删除即可。
- 否则，若 (s_1) 最小的数比左端点的时间大，那么左端点在 (_2) 中，删除即可。
- 否则，左端点在 (s_1) 中，把左端点删除后， (s_1) 不满而 (s_2) 有数，把 (s_2) 中最大的数放入 (s_1)。
于是就可以完成此题了！
Code
#include<bits/stdc++.h>
using namespace std;
int n,w,k,a[200005],t[200005];
int T,res,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]);
int l=1,r=0;
while(r<n)
{
r++;
int tmp=*s1.begin();
if((int)s1.size()<w&&T+(t[r]+1)/2<=k)
s1.insert(t[r]),T+=(t[r]+1)/2,res+=a[r];
else if(t[r]>tmp&&T-(tmp+1)/2+(t[r]+1)/2+tmp<=k)
{
s1.erase(s1.find(tmp));
s1.insert(t[r]);
s2.insert(tmp);
T+=(t[r]+1)/2-(tmp+1)/2+tmp;
res+=a[r];
}
else if(T+t[r]<=k) s2.insert(t[r]),T+=t[r],res+=a[r];
else
{
r--;
if(s1.empty()){r++;continue;}
else if(s2.empty()) s1.erase(s1.find(t[l])),T-=(t[l]+1)/2;
else if(t[l]<tmp) s2.erase(s2.find(t[l])),T-=t[l];
else
{
int ttmp=*--s2.end();
s1.erase(s1.find(t[l]));
s1.insert(ttmp);
s2.erase(s2.find(ttmp));
T=T-(t[l]+1)/2-ttmp+(ttmp+1)/2;
}
res-=a[l];
l++;
}
ans=max(ans,res);
}
printf("%d
",ans);
return 0;
}