#10.23 p1484题解 堆相关

· · 题解

本题基本题意为在n个坑中种至多k棵树，且树与树间不相邻，并使权和最大。

刚看到这个题的时候就想，只要建立一个大根堆并保证每次出堆后，根顶元素互不相邻，然后累加权利就可以了。但实际当然不行！！其实应该考虑拿出一个根顶元素后，那么下次累加一定应选下一个不与它相邻的元素，但这时候就要考虑一个问题了，万一上述情况的权利累加和小于第一次拿出来的根顶相邻的两个元素权利累加和呢？

在详细读了各大神犇的题解后，理解了，当选择了num[i]后，反悔了，反之选择选了num[i-1]和num[i+1]时，获利便增加了num[i-1]+num[i+1]-num[i]。所以当num[i]被选时，我们就可以删去num[i-1]和num[i+1]，即为其代表的book数组打上标记并把num[i]改成num[i-1]+num[i+1]-num[i]，放进堆中，重新找最大的。

而想到这里后，正在学习搜索的我第一时间便想到了多次深搜，即深搜递归中加标记后去标记，但转念一想，先前的错误想法都有超时的数据，那如果用了搜索，岂不是一组也过不去，所以我们要用大根堆存储坑的权利与编号，然后进行上述操作即可。

当取元素取k次或取到元素小于0时结束。 代码如下：

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int n,k;
long long num[500001],ans;//记录权利
int left[500001],right[500001];//记录左右坑 
bool book[500001];//记录遍历过与否
struct node
{
    int id;
    long long w;//w是权利 id是序号 
    bool operator <(node b) const
    {
        return w < b.w;
    }
 } t;//t用来过渡 
priority_queue<node>q;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&t.w);
        num[i]=t.w;
        t.id=i;
        left[i]=i-1;
        right[i]=i+1;
        q.push(t);
    }
    left[n+1]=n;
    right[0]=1;//补全r，l数组
    for(int i=1;i<=k;i++)
    {
        while(book[q.top().id])//如果遍历过则删除 ,注意！一定要用while删除，因为1不知道有几个遍历过。2可能有多次根顶遍历过。 
            q.pop();
        t=q.top();//取出堆顶元素 
        q.pop();
        if(t.w<0)//如果堆顶元素小于0则跳出 
            break;
        ans+=t.w;
        int c=t.id;
        num[c]=num[left[c]]+num[right[c]]-num[c];
        t.w=num[c];//设置新节点，意为若不选x节点选择x节点左右两节点的权利增加量 ，即提供反悔选项。 
        book[left[c]]=book[right[c]]=1;//删除左右的坑
        left[c]=left[left[c]];
        right[c]=right[right[c]];
        right[left[c]]=c;
        left[right[c]]=c;//更新左右坑的左右坑 
        q.push(t);
    }
    printf("%lld",ans);
    return 0;
}