自动搬运

查看原文

来自洛谷，原作者为

	Shunpower 我笨笨的，菜菜的，累累的 >_< | 在役

搬运于2025-08-24 23:14:26，当前版本为作者最后更新于2025-04-25 19:51:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

一道好题。

---

一个贪心的想法是，显然我会希望在某个活动结束后立即睡觉，这样我的可操作空间最大。但是这不行，因为如果活动结束的时刻落在 $[k,2k)$ 之内就不一定可以睡。

考虑一个关键点：如果我们现在在 $[2k,3k]$ 阶段，那么我们是可以想睡就睡的。

所以我们只需要想办法让活动结束在这个阶段内就行。考虑一个结束在 $[k,2k)$ 的活动，如果我希望在这个活动结束后睡觉，那么我只需要减小上一次睡觉的时间就行了！因为睡觉时间可以取任何正整数，而此处 $k\ge 2$，所以一定可以通过调整使得活动结束在 $[2k,3k]$ 内部。

于是我们得出结论：只要有方案，一定存在一种方案使得我必然总是在活动结束后睡觉。

考虑 dp。$f_i$ 表示在第 $i$ 个活动后立即睡觉是否可行。那么考虑转移：$f_i$ 处尝试从第 $j$ 个活动结束后开始立即睡觉，睡觉时间可以取 $t\in(0,b_{j+1}-e_j]$ 的任何数，并要求保持清醒直到 $e_i$。显然，只要满足 $e_i-e_j\le 3(b_{j+1}-e_j)$ 就一定可以找到一个满足要求的 $t$（这个条件说明我们至少存在一个可取的 $t$，我们前面已经说明总是可以调整得到一个 $t$ 使得 $e_i\in[2t,3t]$）。

于是转移是：

$$f_i\gets f_j,\ \ j<i\land e_i-e_j\le 3(b_{j+1}-e_j) $$

我们可以在 dp 过程中记录转移项，然后在最后往回构造。往回构造就是两个不等式，一个限制我们必须在活动结束时位于 $[2t,3t]$，一个限制 $t$，随便解一下就行。

于是我们获得了一个 $\mathcal O(n^2)$ 的做法：

int n;
int dp[N];
int lst[N];
ll b[N],e[N];
vector <pll> ans;
int main(){
#ifdef Shun
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	ios::sync_with_stdio(false);
	cin>>n;
	fr1(i,1,n) cin>>b[i]>>e[i];
	dp[0]=1;
	fr1(i,1,n){
		fr2(j,i-1,0){
			if(dp[j]&&(e[i]-e[j])<=3*(b[j+1]-e[j])){
				lst[i]=j;
				dp[i]=1;
				break;
			}
		}
		// cout<<dp[i]<<endl;
	}
	if(!dp[n]) cout<<"impossible\n";
	else{
		int x=n;
		while(x){
			int id=lst[x];
			ll t=b[id+1]-e[id];
			ll T=e[x]-e[id];
			// cout<<t<<" "<<T<<endl;
			ll k=(T+2)/3;
			ans.push_back({e[id],e[id]+k});
			x=lst[x];
		}
		reverse(ans.begin(),ans.end());
		cout<<ans.size()<<'\n';
		for(auto i:ans) cout<<i.fi<<" "<<i.se<<'\n';
	}
	ET;
}
//ALL FOR Zhang Junhao.

转移显然可以优化，移项之后形如 $e_i\le \text{Poly}(j)$，由于右侧是一个只关于 $j$ 的多项式，所以我们动态维护它的最大值和最大值位置就可以了。只需将 dp 部分改为下面这样即可通过：

maxn=3*b[1];
fr1(i,1,n){
	if(e[i]<=maxn) dp[i]=1,lst[i]=tf;
	if(dp[i]){
		ll coef=3*b[i+1]-2*e[i];
		if(maxn<coef) maxn=coef,tf=i;
	}
	// cout<<dp[i]<<endl;
}

时间复杂度 $\mathcal O(n)$。