BZOJ-2151: 种树

Description

n个位置形成一个环，种m颗树，第i个位置种树有收益ai，相邻位置不能同时种树，i与i+1相邻，n与1相邻，求最大收益。n<=2*10^5

和上一道题一样，每次贪心选出最优的，之后将相邻两个合并。堆+链表实现即可。复杂度nlogn

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000 
int n,m,ans,a[N],pre[N],nxt[N];
bool vis[N];
struct node
{
    int id,w;
};
bool operator < (node x,node y){return x.w<y.w;}
priority_queue<node>q;
int main()
{
    scanf("%d%d",&n,&m);
    if(m>n/2) {puts("Error!"); return 0;}
    int i;
    for(i=1;i<=n;++i)
    {
        pre[i]=i-1; nxt[i]=i+1;
        scanf("%d",a+i);
        q.push((node){i,a[i]});
    }
    pre[1]=n; nxt[n]=1;
    while(m--)
    {
        while(vis[q.top().id]) q.pop();
        i=q.top().id; q.pop();
        ans+=a[i];
        vis[pre[i]]=vis[nxt[i]]=1;
        a[i]=a[pre[i]]+a[nxt[i]]-a[i];
        q.push((node){i,a[i]});
        pre[i]=pre[pre[i]]; nxt[pre[i]]=i;
        nxt[i]=nxt[nxt[i]]; pre[nxt[i]]=i;
    }
    printf("%d",ans);
    return 0;
}