【BZOJ 2151】种树（链表+贪心）

有一种显然错误的做法：每次从堆里取最大的，更新链表

比如 19,20,19 这样的话会先选20。但是很显然，选两个19带来的贡献可能是更好的

这时我们就要想一种能做到“反悔”的方法

其实只需要做一点点修改，每次再push一个“19+19-20”进去，一样是对的

那这个“19+19-20”的放在哪儿呢（编号）？只需要放在20的位置就行了，这样是正确的

其实这样做的本质 是重写了这个问题 将其变成“N-2个物品中选M-1”个的形式，如此一直化归，直到最后变成“N-2(M-1)个物品中选1个”

#include<bits/stdc++.h>
#define N 200005
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0; int f=1;
    static char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')    ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    x*=f;
}
priority_queue<pair<int,int> >q;
int n,m,a[N],l[N],r[N],ans;
bool vis[N];
int main()
{
    read(n),read(m);
    if(m>(n/2)){
        puts("Error!");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        q.push(make_pair(a[i],i));
        l[i]=i-1,r[i]=i+1;
    }
    l[1]=n,r[n]=1;
    while(m--)
    {
        while(vis[q.top().second])  q.pop();
        int val=q.top().first;
        int now=q.top().second;
        q.pop();
        ans+=val, a[now]=a[l[now]]+a[r[now]]-val;
        vis[l[now]]=vis[r[now]]=true;
        l[now]=l[l[now]],r[l[now]]=now;
        r[now]=r[r[now]],l[r[now]]=now;
        q.push(make_pair(a[now],now));
    }
    cout<<ans;
    return 0;
}

转载于:https://www.cnblogs.com/Patrickpwq/articles/9866190.html