P1686 挑战 题解
原题链接
题目大意
\(图上两个x或y值相同的点，如果其没有一条线段直接相连，则这两个点之间的距离为一条捷径\)
\(给定一条路径，求此路径上最短的捷径长度(注意，是捷径最短)以及捷径的起止点和方向\)
数据范围
\(1\le n\le 250000\)
\(先考虑x值相同的情况，假设有3个点A,B,C可以互相构成捷径\)
\(假设A_y>B_y>C_y，则捷径AC<捷径AB,且捷径AC<捷径BC\)
\(所以在x相同的时候，只需按照y值排序，即可使得最短捷径一定在相邻两点之间\)
\(于是可以O(n)求解\)
\(于是贪心方案即为，先把点按x排序，在x相同的时候按y排序\)\
bool cmp1(dian i,dian j)
{
if(i.x==j.x)
return i.y<j.y;
return i.x<j.x;
}
\(可以使用这样的函数加上sort实现\)
\(再考虑y相同的点，其实和x值相同的情况类似，可以用同样方法求解\)
\(复杂度为排序复杂度\)
\(ps:此题要求在捷径长度相同时输出起点编号小的，如果起点编号也相同，则输出终点编号大的，坑死我了\)\
附AC代码
#include<bits/stdc++.h>
using namespace std;
int n,nowx,nowy,top;
struct dian
{
int x,y,d;
}d[300009];
bool cmp1(dian i,dian j)
{
if(i.x==j.x)
return i.y<j.y;
return i.x<j.x;
}
bool cmp2(dian i,dian j)
{
if(i.y==j.y)
return i.x<j.x;
return i.y<j.y;
}
int len,l,r;
char fx;
int main()
{
len=1e9;
cin>>n;
nowx=nowy=2500000;
d[++top]={nowx,nowy,0};
for(int i=1;i<=n;i++)
{
char a;
cin>>a;
if(a=='N')
{
nowy++;
d[++top]={nowx,nowy,i};
}
if(a=='S')
{
nowy--;
d[++top]={nowx,nowy,i};
}
if(a=='E')
{
nowx++;
d[++top]={nowx,nowy,i};
}
if(a=='W')
{
nowx--;
d[++top]={nowx,nowy,i};
}
}
sort(d+1,d+top+1,cmp1);
for(int i=2;i<=top;i++)
{
if(d[i].x!=d[i-1].x)
continue;
if(d[i].y-d[i-1].y<=len)
{
if(abs(d[i].d-d[i-1].d)<=1)
continue;
if(len==d[i].y-d[i-1].y)
{
int ll=d[i-1].d;
int rr=d[i].d;
if(ll>rr)
swap(ll,rr);
if(ll>l)
continue;
if(l==ll&&rr<r)
continue;
l=ll;
r=rr;
if(d[i].d>d[i-1].d)
fx='N';
else
fx='S';
}
else
{
len=d[i].y-d[i-1].y;
l=d[i-1].d;
r=d[i].d;
if(d[i].d>d[i-1].d)
fx='N';
else
{
swap(l,r);
fx='S';
}
}
}
}
sort(d+1,d+top+1,cmp2);
for(int i=2;i<=top;i++)
{
if(d[i].y!=d[i-1].y)
continue;
if(d[i].x-d[i-1].x<=len)
{
if(abs(d[i].d-d[i-1].d)<=1)
continue;
if(len==d[i].x-d[i-1].x)
{
int ll=d[i-1].d;
int rr=d[i].d;
if(ll>rr)
swap(ll,rr);
if(ll>l)
continue;
if(l==ll&&rr<r)
continue;
l=ll;
r=rr;
if(d[i].d>d[i-1].d)
fx='E';
else
fx='W';
}
else
{
len=d[i].x-d[i-1].x;
l=d[i-1].d;
r=d[i].d;
if(d[i].d>d[i-1].d)
fx='E';
else
{
swap(l,r);
fx='W';
}
}
}
}
cout<<len<<' '<<l<<' '<<r<<' '<<fx;
return 0;
}