P7878 「SWTR-07」My rating is 1064(hard version) 题解

发布于 2021-11-15  1.58k 次阅读


题目链接

文章目录

解析

首先第一个帖子肯定会由某一个账号发出。大力观察可以发现当第二个账号发帖之后,接下来一定可以至少两个账号交替发帖,即安全系数不再会有损失。我们仅需要解决第二个账号第一次发帖在哪一个位置即可。

假设我们确定了第二个账号第一次发帖的位置 $i$,那么剩下的 $k-2$ 个账号一定会在 $[i+1,n]$ 中选择 $k-2$ 的最大值进行发帖。因此,我们可以先将第二个账号第一次发帖的位置定在其最晚的可能的位置,然后向前递推。我们用一个堆维护除了第一个账号以外的 $k-1$ 个账号,每向前一个位置,我们就加上对应位置的损失值(这个损失不存在了),并且弹出堆中值最小的元素(不选它了),在强制选择该位置(即加入堆)。

这个过程中贡献值是容易维护的,详见代码(答案最后别忘了加上 $a_1$)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int inf=1e18;
int t,T,n,k,a[N];
priority_queue<int,vector<int>,greater<int> > q;
signed main(){
    scanf("%lld%lld",&t,&T);
    while(T--){
        scanf("%lld%lld",&n,&k);int now=0,ans=-inf;
        while(!q.empty()) q.pop();
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        for(int i=1;i<=n-k;i++) now-=min(a[i],a[i+1]);//损失
        for(int i=n-k+2;i<=n;i++){now+=a[i];q.push(a[i]);}//先选这些元素
        ans=max(ans,now);
        for(int i=n-k+1;i>=2;i--){
            now+=min(a[i-1],a[i]);//减少损失
            now-=q.top();q.pop();//减去最小元素
            now+=a[i];q.push(a[i]);//加入当前元素
            ans=max(ans,now);//更新答案
        }
        printf("%lld\n",a[1]+ans);
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣