自动搬运

查看原文

来自洛谷，原作者为

	极寒神冰 **

搬运于2025-08-24 22:25:18，当前版本为作者最后更新于2022-01-01 17:24:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

一个想法，不知道对不对，就是这个翻译有些细小的偏差

令每张照片的可以拍摄开区间为 $Q_i=(a_i,b_i)$，实际拍摄的开区间 $P_i=(x_i,x_i+t)$，需要有 $P_i\subseteq Q_i$，且 $P_i$ 两两不交。

首先可以想到各种一眼就是错的贪心。

假设现在有 $t=3,Q_1=(0,7),Q_2=(1,4)$。

然后现在从左往右扫，考虑怎么求出 $P_1$。

假如直接贪心把 $(0,3)$ 填上，那么此时 $(1,3)$ 就被覆盖，$P_2$ 无解。

因此，由于问题也只是求是否有解且 $t$ 固定，$Q_2$ 成立也就当且仅当不存在一个 $P_i$ 的左端点在 $(-2,1)$ 中。称这个为 $Q_2$ 禁止区间。

一般化的，对于一个指标集 $S=\{i_1,i_2,\cdots,i_k\}$，设一组合法的方案的区间簇为 $\{P_{i_j}\},i\le j \le k$。其左端点 $\inf(\cup P_i)=N$，左端点 $\inf(\cup Q_i)=M$。则 $S$ 的禁止区间 $F_S=(N-t,M)$。

可以发现，如果存在一组合法方案 $P$，则所有区间的左端点 $a_i=\inf P_i$ 不属于任意一个禁止区间。

然后继续考虑贪心：记所有禁止区间的并集为 $F_x$，从左往右扫，扫的时候跳过 $F_x$ 中的所有点。如果找到某个 $a\ge\inf Q_i$，找到未匹配区间中 $\sup Q_i$ 最小的。然后 $P_i=(a,a+t)$，然后继续从 $a+t$ 开始扫。这样一定可以构造出一组合法的解。

证明可以考虑归纳。。

但是这样子禁止区间高达 $2^n$ 种，考虑减少所需要的禁止区间数量。

令 $S=\{i_1,i_2,\cdots,i_k\}$，$\inf(\cup Q_i)=L,\sup (\cup Q_i)=R$。

如果存在 $x\not\in S$ 满足 $\inf Q_x\ge L$。将 $x$ 加入 $S$ 后，由于需要的区间多了一个 $P_x\subseteq (L,+\infty)$，所以 $\inf ((\cup P_i)\cup P_x)\le \inf(\cup P_i)=N$，$F_S\subseteq F_{S\cup \{x\}}$。

所以事实上 $F_S$ 对禁止区间的并集没有任何贡献，所需要考虑的禁止区间只有 $\mathcal O(n)$ 个：即对于每一个 $a_i$，所有左端点 $\ge a_i$ 的区间构成的集合的禁止区间。（下面的 $F_i$ 表示用上面这句定义的禁止区间）。

考虑按照左端点排序，假设 $a_i<a_{i+1}$。

依次对 $i=n,n-1,\cdots,2,1$ 计算 $F$。

根据前面从左往右的贪心，此时从右往左同样也是对的，答案就是最大的左端点 $N$。

但是这样会出现当前位置不在禁止区间内，但是也没有区间可以匹配。此时可以将这整个问题分成两个更小的子问题，如果出现不可分割的子问题，可以发现一定不存在这种情况。

因此考虑对每一对 $(i,R)$ 维护出只考虑左端点 $\ge a_i$，右端点 $\le R$ 的区间，只考虑不经过禁止区间，不考虑是否有区间匹配，匹配完之后终点数量。

因此

$$\inf F_i=\min \left(a_i,\min\limits_{a_i\le R} (dp_{i,R}-t) \right) $$

然后考虑从 $(i+1,R)$ 转移到 $(i,R)$，因为 $F_i$ 的右端点 $a_i$ 随着 $i$ 递减而递减，因此可以通过双指针跳过禁止区间。

具体，先令 $dp_{i,R}=dp_{i+1,R-t}$，然后由于禁止区间控制的是左端点，因此依次用双指针检验每个 $i$，若当前 $x<a_i$，则对 $\inf F_i$ 取 $\min$ 即可。

判断无解时，就是看 $f_{i,R}$ 是否 $\ge a_i$。

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

#include<bits/stdc++.h>
#define R(i,a,b) for(int i=(a),i##E=(b);i<=i##E;i++)
#define L(i,a,b) for(int i=(b),i##E=(a);i>=i##E;i--)
using namespace std;
int n,t;
pair<int,int>a[11111];
int rr[11111],to[11111],now[11111];
int dp[11111];
inline int ckmin(int &x,const int y)
{
	return x>y?x=y,1:0;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>t;
	R(i,1,n)
	{
		cin>>a[i].first>>a[i].second;
		rr[i]=a[i].second;
	}
	R(i,1,n) now[i]=n;
	sort(a+1,a+n+1),sort(rr+1,rr+n+1);
	R(i,1,n) dp[i]=rr[i],to[i]=1<<30;
	L(i,1,n) 
	{
		int r=n;
		for(;rr[r]>=a[i].second;--r)
		{
			dp[r]-=t;
			for(;i<now[r]&&dp[r]<a[now[r]].first;--now[r]) ckmin(dp[r],to[now[r]]);
			if(dp[r]<a[i].first) return cout<<"no"<<endl,0;
			ckmin(to[i],dp[r]-t);
		}
	}
	cout<<"yes"<<endl;
}