LOJ 2840「JOISC 2018 Day 4」糖

有趣的脑子题（可惜我没有脑子

好像也可以称为模拟费用流（？

我们考虑用链表维护这个东西再把贡献扔到堆里贪心就好了

大概就是类似于有反悔机制的贪心？我们相当于把选中的一个打上一个-v的tag然后如果选了它旁边的就把它取消掉也是一个打tag的思想

说起来不是很好描述看代码可能会更好理解（？

//Love and Freedom.

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#define ll long long

#define inf 20021225

#define pa pair<ll,int>

#define mp make_pair

#define fs first

#define se second

#define N 200001

using namespace std;

int read()

{

    int s=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')    f=-; ch=getchar();}

    while(ch>=''&&ch<='')    s=s*+ch-'',ch=getchar();

    return s*f;

}

int pre[N],nxt[N]; ll val[N];

int a[N],n; bool vis[N];

priority_queue<pa> hp;

void upd(int x)

{

    vis[x]=;

    nxt[pre[x]]=nxt[x];

    pre[nxt[x]]=pre[x];

}

int main()

{

    n=read(); ll ans=; val[]=-1ll*inf*inf; val[n+]=-1ll*inf*inf;

    for(int i=;i<=n;i++)

        val[i]=a[i]=read(),pre[i]=i-,nxt[i]=i+,hp.push(mp(val[i],i));

    for(int i=;i+i-<=n;i++)

    {

        while(vis[hp.top().se])    hp.pop();

        pa tmp=hp.top(); hp.pop();

        ll v=tmp.fs; int pos=tmp.se;

        ans+=v; printf("%lld\n",ans);

        int l=pre[pos],r=nxt[pos];

        val[pos]=val[l]+val[r]-val[pos];

        if(l && r<=n)    hp.push(mp(val[pos],pos));

        upd(l); upd(r);

    }

    return ;

}

巴特西

LOJ 2840「JOISC 2018 Day 4」糖

最新文章

热门文章