这题就是确定一个点，然后去找能够实现最短距离的点且距离最远的点，因为题目要求点最少。在查找时，如果从最后的点开始枚举，找到的第一个满足距离最短的点一定是最远点，但是查找的复杂度是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;
}
如有不当之处欢迎指出！