种树

贪心

题面

一个有$n$个点的带点权环，最大化选取$m$个不相邻的点得到的权值。

• $n\leq2*10^5$

解析

显然可以贪心。
大根堆维护所有点权值。
每次取堆顶点，同时把反悔,选相邻点的影响（$a[L[u]]+a[R[u]]-a[u]$)塞入堆中，并标记相邻两点不可取。

有点卡壳的操作是把$a[u]=a[L[u]]+a[R[u]]-a[u]$，即选在这个坑种树以后将它两边的坑合并为一个价值为（w[l]+w[r]-w[now]）的坑，代替我们选择的坑。
这里非常的巧妙，就是如果选了这个坑就相当于不在那个中间的坑种树了，而是在它两边各种一棵。
可以用链表维护。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100;
struct dat{int w,id;bool operator < (const dat&o) const {return w<o.w;}};
int n,m,a[N],L[N],R[N],vis[N];
ll ans;
priority_queue<dat>Q;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void Del(re int u){L[R[u]]=L[u];R[L[u]]=R[u];}
int main()
{
    n=gi();m=gi();
    if(n/2<m) {puts("Error!");return 0;} 
    fp(i,1,n) a[i]=gi();
    fp(i,1,n) L[i]=i+1,R[i]=i-1;L[n]=1;R[1]=n;
    fp(i,1,n) Q.push((dat){a[i],i});
    while(m--)
    {
        while(vis[Q.top().id]) Q.pop();
        re dat u=Q.top();Q.pop();
        ans+=u.w;
        a[u.id]=a[L[u.id]]+a[R[u.id]]-u.w;
        Q.push((dat){a[u.id],u.id});
        vis[L[u.id]]=vis[R[u.id]]=1;
        Del(L[u.id]);Del(R[u.id]);
    }
    printf("%lld\n",ans);
    return 0;
}