【二分区间长度】【Acwing】机器人移动

博客主页: https://blog.csdn.net/qq_50285142欢迎点赞⭐️收藏⭐️❤️关注❤️留言  如有错误，敬请指正 一看一温习，一码一收获

题目链接：

https://www.acwing.com/problem/content/description/4220/

机器人执行一个指令序列，现可以对一段区间的指令进行替换，修改的指令中，编号最小的指令编号为 minID，编号最大的指令编号为 maxID。我们定义修改成本为 maxID−minID+1，求机器人能够到达目标点 ( a , b ) (a,b) (a,b)最小成本。

二分修改的区间长度（即修改成本），然后对每段长度为mid的区间进行判断。

二分的性质：修改一个长度短的区间可以到达目的地，那么修改长度长的也一定可以到达，因为可以随意修改。那么必然存在一个长度边界ans,满足 l e n ≥ a n s len geq ans len≥ans的全部可以到达目的地， l e n < a n s lenlen

分别计算x和y方向变化量的前缀和dx[],dy[]

c h e c k ( ) check() check()函数：

变量解释：
xx:除修改区间以外的x的变化量,这部分变化量固定，不可修改
yy:除修改区间以外的y的变化量,这部分变化量固定，不可修改
t1:x方向上还需要（即在修改区间中）多少到达目的地
t2:y方向上还需要（即在修改区间中）多少到达目的地对于每一个区间，求出除去修改区间以外的区间还需要多少x和y方向上的变化量来到达目的地 ( x , y ) (x,y) (x,y)对于t1,t2, 首先需要满足 m i d > = a b s ( t 1 ) + a b s ( t 2 ) mid >= abs(t1)+abs(t2) mid>=abs(t1)+abs(t2) ,
其次如果有冗余的长度，即 m i d > a b s ( t 1 ) + a b s ( t 2 ) mid>abs(t1)+abs(t2) mid>abs(t1)+abs(t2) 的情况下，我们需要用两个相反的指令来抵消，
所以还需要满足 ( m i d − a b s ( t 1 ) − a b s ( t 2 ) ) % 2 = = 0 (mid-abs(t1)-abs(t2))%2==0 (mid−abs(t1)−abs(t2))%2==0，另外答案为0和-1的时候先判断一下。

#include
using namespace std;
const int N = 2e5+5;

char s[N];
int dx[N],dy[N];
int n,x,y;

bool check(int mid)
{
	for(int i=1;i+mid-1<=n;i++)
	{
		int l = i,r = i+mid-1;
		int xx = dx[n]-(dx[r]-dx[l-1]);//除修改区间以外的x的变换量
		int yy = dy[n]-(dy[r]-dy[l-1]);//除修改区间以外的y的变化量
		int t1 = x - xx;//x方向上需要多少到达目的地
		int t2 = y - yy;//y方向上需要多少到达目的地
		if(mid >= abs(t1) + abs(t2) && (mid-abs(t1)-abs(t2))%2==0) return true;
	}
	return false;
}
int main()
{
	cin>>n>>s+1>>x>>y;
	for(int i=1;i<=n;i++)
	{
		dx[i] = dx[i-1], dy[i] = dy[i-1];
		if(s[i]=='R') dx[i] ++;
		else if(s[i]=='L') dx[i] --;
		if(s[i]=='U') dy[i] ++;
		else if(s[i]=='D')dy[i] --;
	}
	if(dx[n]==x && dy[n]==y) 
	{
		cout<<0<> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout< 
往期优质文章推荐 
 
 
C++ STL详解，超全总结(快速入门STL) 李【期末复习】c++知识点大回顾，八篇文章让你永不破防（一）区间贡献问题习题详解 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5718474.html