P8175 [CEOI2021] Tortoise

· · 题解

P8175 [CEOI2021] Tortoise

定义一段区域表示一段极大的子区间，其中至少有一个糖果，并且没有垃圾站。

我们可以发现这样一个事实，对于一段区域，一定会先买一些糖，然后丢到这段区域左边的空地上，再买一些糖，丢到这段区域右边的空地上。后半段很好理解，假设在第 j 段区域买了糖，那么我们可以把买的地点下标最大的那颗糖在去第 j+1 段区域的路上顺路扔在第 j 段区域右边的空地上。考虑证明前半段，假设先买了一颗糖丢到右边，再买了一颗糖丢到左边。令这段区域左右两边的空地分别位于 a,d，两次买糖的位置分别位于 b,c，其中 a<b \leq c<d。分别求出两种扔糖方案的距离后可以发现，把 c 扔到右边，把 b 扔到左边优于把 c 扔到左边，把 b 扔到右边。

根据扔的方式不同，我们把所有行动分为三种。第一种：从某个糖出发，把它扔到左边离它最近的空地然后回来。第二种：从某个空地出发，往左走去买一颗糖，然后回来扔掉。第三种：从一个空地出发，买了一颗糖，走到下一个空地扔掉。那么我们会发现，对于每一段区域，我们都会先进行第一种行动，然后进行第三种行动，最后进行第二种行动。

问题在于我们不知道在哪个地方进行哪种行动，进行几次最优。那么我们可以考虑反悔贪心，先尽量扔，扔不了了再调剂。具体的，我们用大根堆维护扔掉每一颗糖需要付出的路程代价，对于每一个糖果商店的 a_{i}-1 颗糖，枚举通过第一种和第二种行动扔掉的个数。如果还可以扔，那么就扔，不然如果堆顶的糖扔掉的代价大于它，那么把堆顶弹掉，相当于不扔堆顶了，转成扔它。那么剩下的那颗糖是干什么的呢？注意到，对于那 a_{i}-1 颗糖，我们只考虑了第一种和第二种行动，第三种行动被我们忽略了，因此剩下的那颗糖就是枚举第三种行动的。

还有一些具体的实现就在代码注释里讲吧。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n;
int a[N],pre[N],nxt[N],to[N];
priority_queue<int> q;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i) cin>>a[i];
    pre[0]=-1e9;
    for (int i=1;i<=n;++i)//找到前一个空地
    {
        pre[i]=pre[i-1];
        if (a[i]==-1) pre[i]=i;
    }
    nxt[n+1]=1e9;
    for (int i=n;i>=1;--i)//找到后一个空地
    {
        nxt[i]=nxt[i+1];
        if (a[i]==-1) nxt[i]=i;
    }
    int last=0;
    for (int i=n;i>=1;--i)//这个数组的含义不太好描述，结合后面理解一下
    {
        if (a[i]==0) continue;
        if (a[i]==-1)
        {
            last=0;
            continue;
        }
        to[i]=last,last=i;
    }
    int sum=0,ans=0;
    for (int i=1;i<=n;++i)
    {
        if (a[i]==-1) continue;
        if (a[i]==0) continue;
        int cnt=a[i]-1,dis=min(i-pre[i],nxt[i]-i)*2;
        while (cnt)
        {
            if (sum<=i-1)//不用乘2的原因是Tom走到i也走了i-1的路程，相当于他只剩下i-1的路程可以继续走
            {
                q.push(dis);
                sum+=dis;
                ++ans,--cnt;
                continue;
            }
            else if (dis<q.top())
            {
                sum-=q.top();
                q.pop();
                --cnt;
                sum+=dis;
                q.push(dis);
                continue;
            }
            else break;
        }
        dis=(i-pre[i])<<1;
        if (!to[i]) dis=0;//直到下一个空地之间都没有有糖的地方，那么就把这颗糖顺路带过去
        else dis=min(dis,(nxt[i]-to[i])<<1);//减to[i]而不是减i是因为这里所有的糖已经考虑完了，不用再回来了
        if (sum<=i-1)
        {
            q.push(dis);
            sum+=dis;
            ++ans;
        }
        else if (dis<q.top())
        {
            sum-=q.top();
            q.pop();
            sum+=dis;
            q.push(dis);
        }
    }
    ans=-ans;
    for (int i=1;i<=n;++i) if (a[i]!=-1) ans+=a[i];
    cout<<ans<<endl;
    return 0;
}