P1686题解

· · 题解

注意：输出的是最短的捷径,而不是最短路径中的捷径

由于捷径一定是直线，我们可以得到 结论1：

  1. 捷径的横坐标(或纵坐标)是相等的。

根据 结论1 ，我们可以分两类讨论，及捷径是横向的或纵向的；

但是这样我们得到的算法是 \mathcal{O}(\text{n}^2) 的，不足以通过此题。

（这毕竟还是道紫题

考虑排序，对于每一类，我们可以按横(或纵)坐标为第一关键字，纵(或横)坐标为第二关键字排序。

易得 结论2:

  1. 排序后对于点 \text{a}_{\text{i}}、\text{a}_{\text{j}}、\text{a}_{\text{k}} (1\le i<j<k\le n)，若 \text{x}_{\text{i}}=\text{x}_{\text{j}}=\text{x}_{\text{k}}，则 (\text{a}_{\text{i}} 和 \text{a}_{\text{j}}) 或 (\text{a}_{\text{j}} 和 \text{a}_{\text{k}}) 形成的捷径一定优于 (\text{a}_{\text{i}} 和 \text{a}_{\text{k}}) 形成的捷径。

所以我们在排序后只需要枚举相邻两点，时间复杂度可以降到 \mathcal{O}(\text{n}\log\text{n})。

但还有一个要点，我们的捷径不能是原来有的边。

这是本题一个难点，大家可以花几分钟想一想；

其实根据 结论2 我们很快可以发现结论3：

  1. 原有的边在排序后一定被分成了长度为 1 的小线段，并且排序前的标号一定会相邻。

所以我们只要在排序前计入标号，判断时查看差是否大于 1 即可。

#include<bits/stdc++.h>
using namespace std;
int n,x,y;char ch;
struct Node {int x,y,nod;} a[250039];
struct anss {int S,E,l;char TO;} ans[2];
bool cmpx(Node x,Node y) {return x.x==y.x?x.y<y.y:x.x<y.x;}
bool cmpy(Node x,Node y) {return x.y==y.y?x.x<y.x:x.y<y.y;}
void print(anss out) {printf("%d %d %d %c\n",out.l,out.S,out.E,out.TO);}
int main() {
    scanf("%d\n",&n);
    for(int i=1; i<=n; i++) {
        ch=getchar();
        switch(ch) {
            case 'N': {a[i]=(Node) {a[i-1].x,a[i-1].y+1,i};break;}
            case 'S': {a[i]=(Node) {a[i-1].x,a[i-1].y-1,i};break;}
            case 'E': {a[i]=(Node) {a[i-1].x+1,a[i-1].y,i};break;}
            case 'W': {a[i]=(Node) {a[i-1].x-1,a[i-1].y,i};break;}
        }
    }
    sort(a+1,a+1+n,cmpx);ans[0]=(anss) {100000000,0,100000000,' '};
    for(int i=1; i<n; i++) {
        (a[i].x==a[i+1].x)&&
        (abs(a[i].nod-a[i+1].nod)>1)&&
        (
            (abs(a[i].y-a[i+1].y)<ans[0].l)||
            (abs(a[i].y-a[i+1].y)==ans[0].l&&((min(a[i].nod,a[i+1].nod)<ans[0].S)||
            (min(a[i].nod,a[i+1].nod)==ans[0].S&&max(a[i].nod,a[i+1].nod)>ans[0].E)))
        )&&
        (ans[0]=(anss) {
            min(a[i].nod,a[i+1].nod),
            max(a[i].nod,a[i+1].nod),
            abs(a[i].y-a[i+1].y),
            (a[i].y>a[i+1].y)^(a[i].nod<a[i+1].nod)?'N':'S'
        },1);
    }
    sort(a+1,a+1+n,cmpy);ans[1]=(anss) {100000000,0,100000000,' '};
    for(int i=1; i<n; i++) {
        (a[i].y==a[i+1].y)&&
        (abs(a[i].nod-a[i+1].nod)>1)&&
        (
            (abs(a[i].x-a[i+1].x)<ans[1].l)||
            (abs(a[i].x-a[i+1].x)==ans[1].l&&((min(a[i].nod,a[i+1].nod)<ans[1].S)||
            (min(a[i].nod,a[i+1].nod)==ans[1].S&&max(a[i].nod,a[i+1].nod)>ans[1].E)))
        )&&
        (ans[1]=(anss) {
            min(a[i].nod,a[i+1].nod),
            max(a[i].nod,a[i+1].nod),
            abs(a[i].x-a[i+1].x),
            (a[i].x>a[i+1].x)^(a[i].nod<a[i+1].nod)?'E':'W'
        },1);
    }
    print((ans[0].l<ans[1].l)?ans[0]:(ans[0].l==ans[1].l?(ans[0].S<ans[1].S?ans[0]:(ans[0].S==ans[1].S?(ans[0].E>ans[1].E?ans[0]:ans[1]):ans[1])):ans[1]));
}