【Educational Codeforces Round 53 (Rated for Div. 2) C】Vasya and Robot

【题解】

如果|x|+|y|>n
显然。从(0,0)根本就没法到(x,y)
但|x|+|y|

【代码】

#include <bits/stdc++.h>

#define ll long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

using namespace std;

const int N = 2e5;

int n;

ll x,y;

ll px[N+10],py[N+10];

char s[N+10];

bool ok(int len){

	rep1(i,1,n){

		if (i+len-1>n) return 0;

	 	ll x0 = px[i-1]-px[0],y0=py[i-1]-py[0];

	 	x0+=px[n]-px[i+len-1];y0+=py[n]-py[i+len-1];

	 	ll temp = abs(x-x0)+abs(y-y0);

	 	if (temp<=len) return 1;

	}

	return 0;

}

int main(){

	#ifdef ccy

			freopen("rush.txt","r",stdin);

	#endif

	scanf("%d",&n);

	scanf("%s",s+1);

	scanf("%lld%lld",&x,&y);

	ll temp = abs(x)+abs(y);

	if (temp>n || ( (temp&1) != (n&1) ) ){

		puts("-1");

		return 0;

	}

	rep1(i,1,n){

		px[i] = px[i-1];py[i] = py[i-1];

	 	if (s[i]=='L') px[i]--;

	 	if (s[i]=='R') px[i]++;

	 	if (s[i]=='U') py[i]++;

	 	if (s[i]=='D') py[i]--;

	}

	int l = 0,r = n,temp1 = -1;

	while (l <= r){

		int mid = (l+r)>>1;

		if (ok(mid)){

		 	temp1 = mid;

		 	r = mid-1;

		}else{

		 	l = mid+1;

		}

	}

	printf("%d\n",temp1);

 	return 0;

}

巴特西

【Educational Codeforces Round 53 (Rated for Div. 2) C】Vasya and Robot

最新文章

热门文章