CodeForces - 1073C（二分）

题解：

二分区间长度，去尺取每一个区间，除去这段区间的操作量，判断现操作距离目的操作所需步数与区间长度作对比，如果是偶数说明可以到达，否则不行。

#include <algorithm>
#include
<iostream>
#include
<cstdlib>
#include
<cstring>
#include
<cstdio>
#include
<string>
#include
<vector>
#include
<bitset>
#include
<stack>
#include
<cmath>
#include
<deque>
#include
<queue>
#include
<list>
#include
<set>
#include
<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define line printf("---------------------------n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;
const double eps = 1e-9;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2000+10;
int n;
int aim_x, aim_y;
int now_x = 0, now_y = 0;
string s;
bool is_ok(int temp_x, int temp_y, int mid){
int need_x = abs(aim_x-temp_x), need_y = abs(aim_y-temp_y);
mid -= need_x;
mid -= need_y;
if(mid < 0){
return false;
}
if(mid % 2 == 0){
return true;
}
return false;
}
bool judge(int mid){
int temp_x = 0, temp_y = 0;
for(int i = 0; i < mid; i++){
if(s[i] == 'U'){
temp_y++;
}
if(s[i] == 'D'){
temp_y--;
}
if(s[i] == 'L'){
temp_x--;
}
if(s[i] == 'R'){
temp_x++;
}
}
if(is_ok(now_x-temp_x, now_y-temp_y, mid)){
return true;
}
for(int i = 1; i+mid-1 < n; i++){
if(s[i+mid-1] == 'U'){
temp_y++;
}
if(s[i+mid-1] == 'D'){
temp_y--;
}
if(s[i+mid-1] == 'R'){
temp_x++;
}
if(s[i+mid-1] == 'L'){
temp_x--;
}
if(s[i-1] == 'U'){
temp_y--;
}
if(s[i-1] == 'D'){
temp_y++;
}
if(s[i-1] == 'R'){
temp_x--;
}
if(s[i-1] == 'L'){
temp_x++;
}
if(is_ok(now_x-temp_x, now_y-temp_y, mid)){
return true;
}
}
return false;
}
int main(){
cin>>n;
cin>>s;
cin>>aim_x>>aim_y;
for(int i = 0; i < n; i++){
if(s[i] == 'U'){
now_y++;
}
if(s[i] == 'D'){
now_y--;
}
if(s[i] == 'L'){
now_x--;
}
if(s[i] == 'R'){
now_x++;
}
}
int l = 0, r = n, ans = -1;
while(l <= r){
int mid = (l+r) >> 1;
if(judge(mid)){
ans = mid;
r = mid-1;
}
else{
l = mid+1;
}
}
printf("%dn", ans);
}

最后

以上就是机智悟空为你收集整理的CodeForces - 1073C（二分）的全部内容，希望文章能够帮你解决CodeForces - 1073C（二分）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。