题解 P1686 【挑战】

· · 题解

第一篇题解？

话说从来没为灰题写过题解诶

好吧开始进入正题

首先因为题目中出了一点岔子，导致有一张图没有显示。不过没关系，这道题目的大意就是：

你有n个操作，每个操作使你向四个方向移动1格，你要找到两个次序不相邻但坐标位于同一平行与坐标轴的直线上的点。

什么，看不懂？

那我们直接开始讲程序

首先我们对坐标进行排序，分别按x和y排。我们先对东西走向的进行操作，再对南北走向的进行操作。

当两点x坐标或y坐标相同时，就判断两点的距离（就是捷径长度），如果这两点原来不是相邻的，那么就记录下来。

#include <bits/stdc++.h>
using namespace std;
struct node{
    int num,x,y;
}a[1111111];
int n,l,r,ll,rr;
int ans;
char dir,d,ch;
bool cmp1(node xx,node yy){//stl用，但最后删掉了（方便pascal党）
    return xx.x<yy.x || xx.x==yy.x && xx.y<yy.y;
}
bool cmp2(node xx,node yy){
    return xx.y<yy.y || xx.y==yy.y && xx.x<yy.x;
}
void qsort1(int l,int r){//这才是真正的快排，按x排序
    int i=l,j=r;
    node k=a[(l+r)/2];
    do{
        while ((a[i].x<k.x)||((a[i].x==k.x)&&(a[i].y<k.y))) i++;
        while ((a[j].x>k.x)||((a[j].x==k.x)&&(a[j].y>k.y))) j--;
        if (i<=j){
            node t=a[i];a[i]=a[j];a[j]=t;
            i++;j--;
        }
    }while (!(i>j));
    if (i<r) qsort1(i,r);
    if (j>l) qsort1(l,j);
}
void qsort2(int l,int r){//按y排序
    int i=l,j=r;
    node k=a[(l+r)/2];
    do{
        while ((a[i].y<k.y)||((a[i].y==k.y)&&(a[i].x<k.x))) i++;
        while ((a[j].y>k.y)||((a[j].y==k.y)&&(a[j].x>k.x))) j--;
        if (i<=j){
            node t=a[i];a[i]=a[j];a[j]=t;
            i++;j--;
        }
    }while (!(i>j));
    if (i<r) qsort2(i,r);
    if (j>l) qsort2(l,j);
}
int init(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%c",&ch);
        while (ch!='W' && ch!='N' && ch!='S' && ch!='E') scanf("%c",&ch);//注意，这句话必须加，否则只能拿80分！！！！！
        a[i]=a[i-1];
        a[i].num=i;//这个点的序号
        if (ch=='E') a[i].y++;
        else if (ch=='W') a[i].y--;
        else if (ch=='N') a[i].x++;
        else if (ch=='S') a[i].x--;//模拟主人公的走动，获得他的坐标
    }
}
bool pd(int x,int y,int z){//判断新的解是否满足题目中杂七杂八的条件
    if (x<ans) return(true);
    if (x>ans) return(false);
    if (l>y) return(true);
    if (l<y) return(false);
    if (r<z) return(true);
    return(false);
}
void doing1(){//两点x坐标相同
    for (int i=1;i<n;++i){
        if (a[i].x==a[i+1].x){
            int dis=a[i+1].y-a[i].y;//两点的距离
            if (a[i].num<a[i+1].num){
                ll=a[i].num;
                rr=a[i+1].num;
                dir='E';//向东
            }
            else{
                ll=a[i+1].num;
                rr=a[i].num;
                dir='W';//向西
            }
            if (ll+1==rr) continue;//如果这两个点相邻，当然满足上面的条件，但是不合题意
            if (pd(dis,ll,rr)){//如果这个解被采纳
                ans=dis;l=ll;r=rr;
                d=dir;
            }
        }
    }
}
void doing2(){//和doing1同理
    for (int i=1;i<n;++i){
        if (a[i].y==a[i+1].y){
            int dis=a[i+1].x-a[i].x;
            if (a[i].num<a[i+1].num){
                ll=a[i].num;
                rr=a[i+1].num;
                dir='N';
            }
            else{
                ll=a[i+1].num;
                rr=a[i].num;
                dir='S';
            }
            if (ll+1==rr) continue;
            if (pd(dis,ll,rr)){
                ans=dis;l=ll;r=rr;
                d=dir;
            }
        }
    }
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);

    init();
    ans=2147483647;
    qsort1(1,n);//可以换成 sort(a+1,a+1+n,cmp1);
    doing1();
    qsort2(1,n);//可以换成 sort(a+1,a+1+n,cmp2);
    doing2();
    printf("%d %d %d %c\n",ans,l,r,d);

    fclose(stdin);
    fclose(stdout);
    return 0;
}

程序比较长，但很多都是快排占用的，C++党只要把两个快排换成stl的就可以了（cmp已经给出）

注意，C++读入的时候必须判断读入的数据的合法性，不然会出错（pascal就没有这么麻烦了）

THE END