题解：P14374 [JOISC 2018] 糖果 / Candies

· · 题解

此题为 P1792 [国家集训队] 种树 的升级版，与原题的区别是此题的序列不是环形的。

考虑使用反悔贪心 + 双向链表。

朴素的贪心是每次选择收益最高的点，并给它左右的节点打上 tag。但有可能出现左右的节点都选的收益比只选这个节点的收益高的情况。

所以我们需要反悔贪心，用大根堆维护当前可进行的操作，选择节点 x 时，删除左右的节点，更新链表，把 x 的权值赋为 v_l + v_r - v_x，并加入堆。再次选到节点 x 时即为放弃节点 x，选择 x 节点的左右节点。

对于不是环形这个问题，其实很好解决，只要将 v_0 和 v_{n+1} 赋为 - \infty 就可以避免选到 0 和 n + 1 的情况。

要记得开 long long，否则过不去样例 2。别问我是怎么知道的

AC CODE

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
ll ans; 
priority_queue<pair<ll,int>>q;
struct node{
    ll val;
    int l,r;
}a[200005];
bool tag[200005];
void del(int x)
{
    a[x].l=a[a[x].l].l;
    a[x].r=a[a[x].r].r;
    a[a[x].l].r=x;
    a[a[x].r].l=x;
}
int main()
{
    cin>>n;
    m=(n+1)/2;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].val);
        a[i].l=i-1;
        a[i].r=i+1;
        q.push({a[i].val,i});
    }
    a[0].val=a[n+1].val=-1145141919810000;
    for(int i=1;i<=m;i++)
    {
        while(tag[q.top().second])q.pop();
        auto x=q.top();q.pop();
        ans+=x.first;
        tag[a[x.second].l]=tag[a[x.second].r]=1;
        a[x.second].val=a[a[x.second].l].val+a[a[x.second].r].val-a[x.second].val;
        q.push({a[x.second].val,x.second});
        del(x.second);
        printf("%lld\n",ans);
    }
    return 0;
}