CodeForces-748C

这题就是确定一个点，然后去找能够实现最短距离的点且距离最远的点，因为题目要求点最少。在查找时，如果从最后的点开始枚举，找到的第一个满足距离最短的点一定是最远点，但是查找的复杂度是O(n)，共有n次查找，O(n^2)的复杂度题目数据无法承受，因此可以考虑二分查找，以起点的下一个点直到最后一个点的区间作为查找对象，每次选取中点作为更新区间的上限和下限的标准，如果中点到起点是最短距离就更新下限为中点，否则上限是中点，推出的时候处理一下就行。之所以能够这样更新区间是因为，如果有一个点不能满足最短距离，那么在它后面的点也无法满足最短距离。

AC代码：

#include<cstdio>
const int maxn=2e5+5;
char s[maxn];
struct node{
	int x,y;
	node(){}
	node(int x,int y):x(x),y(y){
	}
}p[maxn];
int abs(int a){
	return a<0?(-a):a;
}
int bound(int x,int y){
	int z=x-1;
	while(x<y){
		int k=(x+y)/2;
		int d=abs(p[k].x-p[z].x)+abs(p[k].y-p[z].y);
		int h=k-z;
		if(d==h) x=k;
		else if(d<h) y=k;
		if(x==y-1) break;
	}
	return x;
}
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		scanf("%s",s);
		int x=0,y=0;
		p[0]=node(0,0);
		for(int i=1;i<=n;++i){
			if(s[i-1]=='R') ++y;
			else if(s[i-1]=='L') --y;
			else if(s[i-1]=='U') --x;
			else ++x;
			p[i]=node(x,y);
		}
		int ans=0;
		for(int i=0;i<n;){
		//利用二分查找实现快速查找  否则会超时
			i=bound(i+1,n+1);
			++ans;
		}
		printf("%d\n",ans);
	}
	return 0;
}

如有不当之处欢迎指出！

巴特西

CodeForces-748C

最新文章

热门文章