自动搬运

查看原文

来自洛谷，原作者为

	ReseeCher AFO·运气选手

搬运于2025-08-24 22:22:36，当前版本为作者最后更新于2020-07-01 21:52:36，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

约定覆盖位置$[l]$,$[l+1]$,$[l+2]$......$[r]$的为一条从$l$开始的“直线”

约定覆盖位置$[l]$,$[l+2]$,$[l+4]$......$[r]$的为一条从$l$开始的“跳线”

那么原问题相当于使用一些直线和跳线使每个位置$i$刚好被$a[i]$条线覆盖

每用一条线称作$1$个$cost$,我们希望总的$cost$最小

首先考虑如何去覆盖第$1$和第$2$个位置

为了方便，这里$a[i]$表示位置$i$还要被几条线段覆盖

这里先给出方案：

1. $(a[1]>0,a[2]=0)$：从$a[1]$开始一条跳线

2. $(a[1]>0,a[2]>0)$：从$a[1]$开始一条直线

3. $(a[1]=0)$：暂时不决策

$prove1$

比较显然，位置$2$已经不能被覆盖，只能连出跳线

$prove2$

考虑证明以下命题：从1开始的连续非0区间（长度>=2）用一条直线覆盖一定不劣

设这段区间为$[1,r]$，那么因为$a[r+1]=0$，所以不可能向后连出直线，唯一有利于后面位置被覆盖的方案是在与$(r)$奇偶性相同的位置连出一条跳线

但是这样做必有$cost>=2$，而使用一条直线和一条跳线$cost$为$2$，所以一定不优于原方案（不如从后面开始跳线）

此时由于$a[1]=0$了，我们可以把位置$1$删除，继续考虑第$2$和第$3$个位置

这个问题与刚才的问题类似，唯一的区别是要处理被前面开始的线覆盖的情况

如果能被前面的线覆盖则一定被覆盖，因为这样$cost=0$，而任意一种可能更利于后面被覆盖的方案都需要$cost=1$，不如从后面开始

若前面的直线有$A$个，能连到$3$的跳线有$B$个

那么如果$a[3]>=A+B$，直接把$a[3]$减去$A+B$即可

但如果$a[3]<A+B$，则一定有$A+B-a[3]$条线无法连下去，记为$K$

发现保留直线还是跳线和后面的位置有关，于是我们可以先把A和B都减去$K$，再在$3$上打$K$个标记，表示可以从$3$免费开始$K$条任意的线

但这时候出现了一个新的问题，$A$和$B$不能被减到负数

注意到若$K>A$，那么$B$至少也要断掉$K-A$条，那么先把这些边断掉，这样就没有问题了

$K>B$时同理

这样我们就有一个可以从$(a[i-1],a[i])$推到$(a[i],a[i+1])$的算法了，一遍推过去即可

具体可以看代码中的注释

void Work(){
	LL A=0,B=0,C=0,Ans=0,D=0;			//C表示奇偶性为另一类的跳线个数 
	F(i,2,n+1){
		if(a[i]<B+A){					//处理被前面的线覆盖的情况
			int K=B+A-a[i];
			if(B<K)A-=K-B,K-=K-B;
			if(A<K)B-=K-A,K-=K-A;
			B-=K;A-=K;a[i]-=K;D=K;		//D：记录标记个数 
		}
		a[i]-=A+B;
		
		LL U=min(a[i-1],a[i]);			//U：新增直线个数 
		Ans+=U;a[i-1]-=U;a[i]-=U;A+=U;	//处理直线 
		Ans+=a[i-1];C+=a[i-1];a[i-1]=0;	//处理跳线 
		
		a[i]+=D;Ans-=D;D=0;				//处理标记 
		swap(B,C);						//奇偶性互换 
	}
	cout<<Ans<<'\n';
}