【bzoj2151】种树（堆/优先队列+双向链表）

　　题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2151

　　这道题因为优先队列不怎么会用，而且手写堆的代码也不长，也想复习一下手写堆的写法……结果……WAWAWAWAW……看来我对堆的认识还是太浅薄了……

　　这道题，如果没有限制不能选相邻的两个位置，那就肯定是贪心地选择m个美观度最大的位置种树。然而这里加了限制，那么我们可以注意到，如果一个美观度比较大的位置不被选上，一定是因为它两边的位置都被选了。

　　于是我们可以把n个美观度压进一个堆里，每次把美观度最大的位置取出来更新答案，然后它两边的位置删掉，把这个位置的美观度修改成（左边的美观度+右边的美观度-原美观度），就是选这个位置与选两边位置的权值差。

　　如果细节没有打错，然后就可以愉快地AC这道题了。

　　跑的慢也不会赢的代码：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<ctime>

#include<algorithm>

#include<queue>

#include<vector>

#include<map>

#define ll long long

#define inf 1<<30;

#define min(a,b) (a<b?a:b)

#define max(a,b) (a>b?a:b)

ll read()

{

    ll tmp=; char f=,c=getchar();

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

    while(''<=c&&c<=''){tmp=tmp*+c-''; c=getchar();}

    return tmp*f;

}

using namespace std;

struct data{

    int w,id;

}hp[];

int l[],r[],pos[];

int n,m,tot=;

void swap(int x,int y)

{

    data tmp=hp[x]; hp[x]=hp[y]; hp[y]=tmp;

    pos[hp[x].id]=x; pos[hp[y].id]=y;

}

void add(int id,int w)

{

    hp[++tot].id=id; hp[tot].w=w; pos[id]=tot;

    for(int now=tot;now>&&hp[now].w>hp[now>>].w;now>>=)swap(now,now>>);

}

void sift(int x)

{

    int now=x;

    while(now<<<=tot){

        int ne=now<<;

        if(ne<tot&&hp[ne].w<hp[ne+].w)++ne;

        if(hp[ne].w>hp[now].w)swap(ne,now),now=ne;

        else break;

    }

}

void del(int id)

{

    hp[pos[id]].w=-inf; sift(pos[id]);

    r[l[id]]=r[id]; l[r[id]]=l[id];

}

int main()

{

    int i;

    n=read(); m=read();

    if(n<m*){

        printf("Error!\n"); return ;

    }

    for(i=;i<=n;i++)add(i,read()),l[i]=i-,r[i]=i+;

    l[]=n; r[n]=;

    ll ans=;

    while(m--){

        ans+=hp[].w;

        int id=hp[].id;

        hp[].w=hp[pos[l[id]]].w+hp[pos[r[id]]].w-hp[].w; sift();

        del(l[id]); del(r[id]);

    }

    printf("%lld\n",ans);

    return ;

}

bzoj2151