CodeForces - 1236D Alice and the Doll(贪心+二分+模拟)

题目链接：点击查看

题目大意：给出一个n*m的矩阵，矩阵中有k个障碍物，在点(1,1)处有一个洋娃娃，洋娃娃每次的行动路线只能是直走或右拐，初始时洋娃娃面朝正右方向，问洋娃娃能否将所有方格都走一遍，并且只走一次（不包括障碍物）

题目分析：n和m的范围都到达了1e5，如果暴力跑的话时间复杂度能到1e10，肯定会T，那我们有什么好的方法来优化呢？这个题目其实可以借助贪心的思想先分析一波，首先，若整个矩阵中没有障碍物，那么洋娃娃的行走路线肯定是一个螺旋矩阵的路线，大概就是蛇形填数的那种题目一样，再就是通过分析可以得到，当洋娃娃可以选择直走或右拐的时候，肯定会选择直走而不是右拐，为什么呢？因为洋娃娃一旦右拐，就无法到达原本直走可以到达的方格了，并且随着洋娃娃转弯次数的变多，洋娃娃可行走的区域，也就是可移动的矩阵会越来越小，（虽然不会证明，但不难看出），于是我们可以每次贪心移动，让洋娃娃都到达直走可到达的最远距离（障碍物或边界）前停下，然后右拐，并实时维护一直在缩小的可移动矩阵，通过模拟上述过程得到步数，累加后和空白的方块数量比对一下就能判断是否达到题目要求了

现在我们的问题就是转换成怎么样能比较快速的找到面前的障碍物了，我们可以对于每一行x和每一列y都维护一个数组，当然我是为了方便操作，加上为了让代码更加简洁起见，用了vector来代替数组，储存每一行以及每一列的障碍物，这样我们就可以二分了，每次直走的时候都会保证x或y不变，我们只需要二分找到下一个障碍物即可，然后再判断一下障碍物的位置和可行范围的大小，就能确定直走可以达到的最大位置了，如此往复模拟上述操作，时间复杂度应该就是nlogn

对了，看网上有人用set维护的障碍物坐标，我感觉没必要，因为题目已经保证了不会有两个障碍物在同一个方格上，我还是习惯用vector+sort

对了，这个题目如果按照上述思路基本上是没问题的，不过还有一个小细节需要注意一下，因为我们在正常情况下每次先直走到头，然后右拐后再直走到头，走到最后肯定是无法直走的时候结束循环，但还有一个比较特殊的情况需要我们特判一下，那就是在一开始就需要右拐的情况，若按照上述思路编出来的代码是无法通过下面的样例的：

2 1 0

正确答案应该是Yes，但上面的思路给出的答案却是No，为了解决这种特例，我们可以在一开始加一个first的布尔变量，用来让起点可以直走，可以直接右拐

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;vector<int>X[N],Y[N];//储存障碍物，为二分做准备int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=k;i++){int x,y;scanf("%d%d",&x,&y);X[x].push_back(y);Y[y].push_back(x);}for(int i=1;i<=n;i++)sort(X[i].begin(),X[i].end());for(int i=1;i<=m;i++)sort(Y[i].begin(),Y[i].end());int up=0,down=n+1,left=0,right=m+1;LL ans=1;//答案初始化为1，因为题目保证了在点(1,1)处不会有障碍物int x=1,y=1;//当前坐标int pos=0;//当前方向bool first=false;//特判一下起点while(true){int tx,ty;if(pos==0)//→ {int j=lower_bound(X[x].begin(),X[x].end(),y)-X[x].begin();tx=x;if(j==X[x].size())ty=right-1;elsety=min(right-1,X[x][j]-1);up=x;}else if(pos==1)//↓ {int j=lower_bound(Y[y].begin(),Y[y].end(),x)-Y[y].begin();ty=y;if(j==Y[y].size())tx=down-1;elsetx=min(down-1,Y[y][j]-1);right=y;}else if(pos==2)//← {int j=lower_bound(X[x].begin(),X[x].end(),y)-X[x].begin()-1;tx=x;if(j<0)ty=left+1;elsety=max(left+1,X[x][j]+1);down=x;}else if(pos==3)//↑ {int j=lower_bound(Y[y].begin(),Y[y].end(),x)-Y[y].begin()-1;ty=y;if(j<0)tx=up+1;elsetx=max(up+1,Y[y][j]+1);left=y;}if(tx==x&&ty==y&&first)//若走不动了，及时跳出循环break;pos=(pos+1)%4;//走到头后右拐ans+=abs(tx-x)+abs(ty-y);//答案取一下曼哈顿距离即可x=tx;//迭代y=ty; first=true;//让洋娃娃可以从起点直接右拐}if(ans==1LL*n*m-k)//记得开longlong，因为n*m到达了1e10printf("Yes\n");elseprintf("No\n");return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1236D Alice and the Doll(贪心+二分+模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。