题解 P7405 [JOI 2021 Final] 雪玉

洛谷。

题意

应该好理解的。

分析

我们的所有雪球在同一时间之间的距离都是相同的，因此一段雪，要么是它左侧的第一个所取，要么右侧第一个所取，要么不被取，并且，我们每一个雪球所占有的雪是连续的一段。

我们令 \(L_i\) 表示第 \(i\) 步前所能走的最左点，\(R_i\) 表示第 \(i\) 步前所能走的最后点。

我们分析两个雪球初始位之间的雪地的分割情况，两点间距离为 \(len\)：

1. 左侧与右侧并不相接，即 \(R_m-L_m\le len\)，那么左侧的雪球就可以增加 \(abs(L_m)\)，右侧雪球就可以增加 \(R_m\)。
2. 会有某一段收到两个争夺，那么，我们先找到最大的 \(k\)，使得 \(R_k-L_k\le len\)，先将这一段分割，接着，假如说这一步是向左，那么这一段就是属于右侧的，假如说这一步是向右，那么这一步就属于左侧，因为这一步过后，这一段必然会被某一端所占领。

a[0]=-INF,a[n+1]=INF;
int mx=lenth[m];
for(int i=1; i<=n+1; ++i) {
	int len=a[i]-a[i-1];
	if(len>=mx) {
		ans[i]+=abs(L[m]);
		ans[i-1]+=abs(R[m]);
	} else {
		int T=upper_bound(lenth+1,lenth+m+1,len)-lenth-1;
		ans[i]+=abs(L[T]),ans[i-1]+=abs(R[T]);
		if(b[T+1]>0) ans[i-1]+=len-lenth[T];
		else ans[i]+=len-lenth[T];
	}
}