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

· · 题解

分析

这种长得很像 dp 但是复杂度显然有问题的题应当考虑贪心。但是发现正常贪心不行，所以考虑反悔贪心。

对于反悔操作，考虑原本选了 x，会导致 x-1 和 x+1 选不了。反悔之后，当然希望同时选回这两个数（x-2 或者 x+2 选了的情况之后会说明），于是相当于选下 x 之后往贪心的优先队列里面加入一个反悔后的 x，即价值为 a_{x-1}+a_{x+1}-a_x 的一个数。

发现一个点，选了 x 是要删除 x-1 和 x+1 的，本质上会相当于一个链表的删除操作。所以上面的 x-1 和 x+1 实际上对应链表上 x 的前驱和后继。这时候就不用考虑 x-2 和 x+2 的情况。因为比如选了 x-2，那么 x-1 就不会在链表里面了，这时候 x 的前驱本质上是“反悔 x-2 的选择”，所以不会与题意矛盾。

另外使用链表还可以避免反悔一次找不回来的情况，因为在原位置插入“反悔操作”实际上允许了反悔之前的反悔操作，反悔反悔之前的反悔操作……所以每一次选择其实都是可以考虑到所有情况的。

每次选择要么直接选一个出来，要么反悔一个选两个出来，必定多选一颗糖，所以选 \lceil \frac n 2\rceil 次即可。

AC Code


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
int l[N],r[N],vis[N],a[N];
inline void del(int x)
{
    r[l[x]]=r[x];
    l[r[x]]=l[x];
    vis[x]=1;
}
signed main()
{
    int n;
    cin>>n;
    a[0]=a[n+1]=-1e18;
    for(int i=1;i<=n;i++) cin>>a[i],l[i]=i-1,r[i]=i+1;
    r[n+1]=n+1;
    priority_queue<pair<int,int>> q;
    for(int i=1;i<=n;i++) q.push({a[i],i});
    int ans=0,cnt=0;
    while(cnt<(n+1)/2)
    {
        auto [w,x]=q.top();
        q.pop();
        if(vis[x]) continue;
        cnt++;
        ans+=w;
        cout<<ans<<'\n';
        a[x]=a[l[x]]+a[r[x]]-a[x];
        if(l[x]>=1&&r[x]<=n) q.push({a[x],x});
        del(l[x]);del(r[x]);
    }
}