自动搬运

查看原文

来自洛谷，原作者为

	北文 月光下转身

搬运于2025-08-24 23:00:59，当前版本为作者最后更新于2024-07-17 20:27:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

建议管理增加描述：
要覆盖所有时间而不是所有整点！（调了很久）

那么讲讲这题怎么做。
这题有个很显然的贪心策略：如果已经选取了一段，那么在选取的这段中，选取能往后延伸最长的那一个进行扩展。
但是也有一个显然的问题，那就是不知道第一个取哪一个。怎么确定呢，枚举吗？也许只能枚举。
那么我们考虑加速这个贪心过程。选取哪一个作为第一个并不影响每一个位置的决策，考虑用倍增进行优化。
记 $f[i][j]$ 表示在第 $i$ 个位置再选取 $2^j$ 个人能到达什么位置，f 数组的计算可以用 dp，这都是比较简单的。
还有就是数据范围太大需要离散化处理。

我的代码是建立在覆盖所有整点的题意上改过来的，所以有亿点丑。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5, inf=1e9;
int n, lsh[N*3], m, cn, f[N*3][21], nn;
pair<int, int> a[N*3], b[N*3];
#define fi first
#define se second
bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.fi<b.fi; 
}
inline void ckmax(int &x, int y) { if(y>x) x=y; }
int main() {
	scanf("%d %d", &n, &nn);
	for(int i=1; i<=n; i++) {
		scanf("%d %d", &a[i].fi, &a[i].se);
		lsh[++m]=a[i].fi; lsh[++m]=a[i].se;
		if(a[i].fi!=0)
		lsh[++m]=a[i].fi-1; 
		if(a[i].se!=0)
		lsh[++m]=a[i].se-1;
		if(a[i].fi!=nn-1)
		lsh[++m]=a[i].fi+1; 
		if(a[i].se!=nn-1)
		lsh[++m]=a[i].se+1;
	}
	lsh[++m]=nn-1;
	lsh[++m]=0;
	sort(lsh+1, lsh+1+m);
	m=unique(lsh+1, lsh+1+m)-lsh-1;
	for(int i=1; i<=n; i++)
		a[i].fi=lower_bound(lsh+1, lsh+1+m, a[i].fi)-lsh-1,
		a[i].se=lower_bound(lsh+1, lsh+1+m, a[i].se)-lsh-1; 
	for(int i=1; i<=n; i++) {
		if(a[i].fi<a[i].se) {
			b[++cn]=a[i];
			b[++cn]={a[i].fi+m, a[i].se+m};
		} else {
			b[++cn]={a[i].fi, a[i].se+m};
		}
	}
	for(int i=1; i<=cn; ++i) {ckmax(f[b[i].fi][0], b[i].se);}
	for(int i=0; i<=m*2; ++i) {ckmax(f[i+1][0], f[i][0]);}
	for(int k=1; k<=18; ++k) {
		for(int i=0; i<=m*2; ++i)
			f[i][k]=f[f[i][k-1]][k-1];
		for(int i=0; i<=m*2; ++i)
			ckmax(f[i+1][k], f[i][k]);
	}
	int ans=inf;
	for(int i=0; i<m; ++i) {
		int u=i, t=0;
		for(int k=18; k>=0; --k) {
			if(f[u][k]<=i+m-1) {
				t+=1<<k; 
				u=f[u][k];
			}
		}
		if(f[u][0]>i+m-1) {
			ans=min(ans, t+1);
		}
	}
	if(ans>=inf) printf("-1\n");
	else printf("%d\n", ans);
	return 0;
}