P1686 挑战题解

__shadow__ · 2022-07-11 14:33:00 · 题解

本题就是要找到最短的捷径。

注意事项：

捷径必须是直线。
要求捷径最短而非总路程最短。
捷径不与原有的路重合

既然在同一直线上，则该捷径的起点与终点的横坐标或纵坐标相等。要把横坐标或纵坐标相同的聚在一起只需要排个序即可。

捷径最短的话（以横坐标相等举例），只需要以 x 为第一关键字，以 y 为第二关键字排序后，找相邻的两个并求最短就好。

不与原有路径重合。因为把每一个点都记下来了，所以起点与终点的序号只差 1 就说明原来已有路径。

分析结束，看代码。

#include<algorithm> 
#include<cstdio>
using namespace std;
const int N = 250000 + 5;
struct node
{
    int x, y, id;//x,y 为横纵坐标; id 是序号 !:从1开始 
}a[N];
bool cmpx(node a, node b)//以 x 为第一关键字 
{
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmpy(node a, node b)//以 y 为第一关键字 
{
    return a.y == b.y ? a.x < b.x : a.y < b.y;
}
int n;
char s[N];
struct stsearr//答案,整合后方便赋值 
{
    int lenth;//长度 
    int head, tail;//起点和终点 
    char fang;//方向 
}ans;
void do_x()//查找竖的捷径 
{
    stsearr t;
    for (int i = 2;i <= n; i++)
    {
        if (a[i].x == a[i - 1].x)//竖着的直线 
        {
            t.lenth = a[i].y - a[i - 1].y;//排序中以从小到大 
            if (a[i].id < a[i - 1].id)//id 小的是起点 
            {
                t.fang = 'S';
                t.head = a[i].id;
                t.tail = a[i - 1].id;
            }
            else
            {
                t.fang = 'N';
                t.head = a[i - 1].id;
                t.tail = a[i].id;
            }
            if (t.head + 1 == t.tail)//判断是否与原有路径重合 
                continue;
            if (t.lenth < ans.lenth)//更新答案 
                ans = t;
            else if (t.lenth == ans.lenth)
            {
                if (t.head < ans.head)
                    ans = t;
                else if (t.head == ans.head)
                    if (t.tail > ans.tail)
                        ans = t;
            }
        }
    }
}
void do_y()//查找竖的捷径 
{
    stsearr t;
    for (int i = 2;i <= n; i++)//与上同理 
    {
        if (a[i].y == a[i - 1].y)
        {
            t.lenth = a[i].x - a[i - 1].x;
            if (a[i].id < a[i - 1].id)
            {
                t.fang = 'W';
                t.head = a[i].id;
                t.tail = a[i - 1].id;
            }
            else
            {
                t.fang = 'E';
                t.head = a[i - 1].id;
                t.tail = a[i].id;
            }
            if (t.head + 1 == t.tail)
                continue;
            if (t.lenth < ans.lenth)
                ans = t;
            else if (t.lenth == ans.lenth)
            {
                if (t.head < ans.head)
                    ans = t;
                else if (t.head == ans.head)
                    if (t.tail > ans.tail)
                        ans = t;
            }
        }
    }
}
signed main()
{
    scanf ("%d", &n);
    scanf ("%s", s + 1);
    //小技巧:这样可以从 1 下标开始读入 
    for (int i = 1;i <= n; i++)
    {
        a[i].id = i;
        a[i].x = a[i - 1].x;
        a[i].y = a[i - 1].y;
        if (s[i] == 'N')//处理四种方向 
            a[i].y++;
        else if (s[i] == 'E')
            a[i].x++;
        else if (s[i] == 'W')
            a[i].x--;
        else if (s[i] == 'S')
            a[i].y--;
    }
    ans.lenth = 1e9;//找最小值,赋最大值 
    sort(a + 1, a + n + 1, cmpx);
    do_x();
    sort(a + 1, a + n + 1, cmpy);
    do_y();
    printf ("%d %d %d %c", ans.lenth, ans.head, ans.tail, ans.fang);
    return 0;
}

希望可以帮到大家。

如有错误欢迎私信指出。

P1686 挑战 题解

P1686 挑战题解