Bubble Cup 8 finals F. Bulbo (575F)

题意：

给定初始位置，查询n次区间，每次查询前可以花费移动距离的代价来移动，

查询时需要花费当前位置到区间内最近的点的距离，求最小代价。

1<=n<=5000，1<=所有位置<=10^9

题解：

可以用O(n^2)的暴力DP碾过去…

不过实际上可以O(n)贪心。

贪心的想法是比较明显的，就是每次找最近的，需要考虑的就是移动不移动。

比如有多个连续的在当前位置左边的区间，

这时往左会让这些区间的答案都减小，而增大的代价至多是移动距离*2。

不过这样子考虑会比较麻烦，观察到这题的特点，在查询时花费代价或者移动后再查询花费代价是一样的。

所以我们可以用一个区间表示当前位置（当前答案对应的可能的位置区间）。

这样，如果查询区间完全在当前区间之外，就一定要增加代价，

代价最小就是当前区间里查询区间最近的点，然后可以更新当前区间为这个点到查询区间之间的范围。

（在这个范围内的任何一点的移动代价+查询代价都是一样的）

如果查询区间包含了当前区间，就代表当前区间的任何一点都不用增加代价。

如果查询区间与当前区间只有部分重合，那么重合部分不用增加代价，所以就把当前区间缩小到重合部分。

这样就实现了贪心。

#include <cstdio>

#include <cstring>

inline int read()

{

	int s = ; char c; while((c=getchar())<'0'||c>'9');

	do{s=s*+c-'0';}while((c=getchar())>='0'&&c<='9');

	return s;

}

int n,l,r,ql,qr;

long long ans;

int main()

{

	for(n=read(),l=r=read();n--;)

	{

		ql = read(), qr = read();

		if(ql<=l&&r<=qr) continue;

		if(qr<l) ans += l-qr, r = l, l = qr;

		else if(r<ql) ans += ql-r, l = r, r = ql;

		else l = ql>l?ql:l, r = qr<r?qr:r;

	}

	printf("%I64d\n",ans);

	return ;

}

巴特西

Bubble Cup 8 finals F. Bulbo (575F)

最新文章

热门文章