题解 P1792 【种树】

· · 题解

P1792题解

传送门

题意简述

给出一个 n 个有权值节点的环，选出 m 个不相邻的节点，使它们的权值和最大。

m<=n<=2*10^5

题目分析

如果 m = 1，那么结果就是a数组中的最大值。

如果 m = 2，那么就有两种情况：

  1. 选择最大值 a_i ，不选 a_{i-1} ,a_{i+1} ，再从剩下的数中选择最大值。
  2. 不选最大值 a_i ，选 a_{i-1} ,a_{i+1} 。

为什么不选最大值 a_i 就要选 a_{i-1} ,a_{i+1} 呢？

如果只选了 a_{i-1} ,a_{i+1} 中的一个，那么把选了的换成了 a_i 一定更优。

显然a_i , a_{i-1} ,a_{i+1} 都不选不是最优解。

所以最大值左右两侧的数要么都选，要么都不选。

所以我们可以先选上 a 数组中的最大值（第一种情况），然后将然后将 a_{i-1},a_i,a_{i+1} 从数列中删除，并在原位置插入一个新元素a_{i-1}-a_i+a_{i+1} 。这样原问题就变成了一个从 a数组中选 m-1 的数的子问题，显然重复这个操作 m-1次就可以求出最终结果。

代码实现思路

所以我们可以建立一个链表 Q，分别记录a_1,a_2,a_3 … a_{N-1} 。 再建立一个二元组大根堆，每个元素与链表中的每一个元素成一一映射关系，第二元记录对应链表中的指针。

每次取出堆顶，更新答案。再删除节点（链表中打标记、更新左右节点数组，大根堆中删除）、插入新节点。

执行m次后输出。

易错点

AC代码

内带详细注释

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define N 500002
using namespace std;
void read(long long &x){
    int f=1;x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
long long a[N],le[N],r[N],ans;
bool v[N];
priority_queue < pair < int , int > > q;
void del(int x){//删除操作 
    le[r[x]]=le[x];
    r[le[x]]=r[x];
    v[x]=1;//该点是否被删除 
}
int main(){
    int n,m;
    cin>>n>>m;
    le[1]=n;r[1]=2;le[n]=n-1;r[n]=1;//处理首尾 
    for(int i=1;i<=n;i++){//读入 
        read(a[i]);
    }
    if(n<m*2){//判断 
        printf("Error!");
        return 0;
    }
    for(int i=2;i<n;i++) le[i]=i-1,r[i]=i+1;//建立链表 
    for(int i=1;i<=n;i++){
        q.push(make_pair(a[i],i));//第一元为值，第二元为标号 
    }
    while(m--){
        int x,y;
        while(v[q.top().second]) q.pop();//忽略删除的节点
        y=q.top().second;q.pop();//取出最大节点 
        ans+=a[y];//更新答案 
        a[y]=a[le[y]]+a[r[y]]-a[y];//新节点 
        del(le[y]);del(r[y]);//删除左右节点 
        q.push(make_pair(a[y],y)); 
    }
    printf("%d",ans);
}