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

题目链接

解析

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

假设我们确定了第二个账号第一次发帖的位置 $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;
}
本文作者:water_tomato

评论

  1. rantrism
    2 年前
    2022-12-15 16:19:02

    您好~我是腾讯云开发者社区运营,关注了您分享的技术文章,觉得内容很棒,我们诚挚邀请您加入腾讯云自媒体分享计划。完整福利和申请地址请见:https://cloud.tencent.com/developer/support-plan

    作者申请此计划后将作者的文章进行搬迁同步到社区的专栏下,你只需要简单填写一下表单申请即可,我们会给作者提供包括流量、云服务器等,另外还有些周边礼物。

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇