自动搬运

查看原文

来自洛谷，原作者为

	ZSR **

搬运于2025-08-24 22:36:36，当前版本为作者最后更新于2023-10-31 18:10:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}