题解：AT_abc258_f [ABC258F] Main Street

前置

题目大意

在平面直角坐标系中，所有直线

x=n

和

y=n

（

n

为整数）都是道路。其中，直线

x=Bn

和

y=Bn

被称为大通道。

高桥君可以从

(x,y)

移动到相邻的四个点

(x\pm1,y)

或

(x,y\pm1)

：

如果沿着大通道移动，花费 $1$ 秒；
否则花费 $K$ 秒。

求从

(S_x,S_y)

到

(G_x,G_y)

的最短时间。

解题思路

如果不利用大通道，直接曼哈顿距离移动，花费时间为：

dis=|S_x−G_x|+|S_y−G_y|,time=dis\times K

。

对于起点

(S_x,S_y)

，找到它上下左右四个方向最近的大通道：

上方大通道： $y=\lceil\frac{S_y}{B}\rceil\times B$ ；
下方大通道： $y=\lfloor\frac{S_y}{B}\rfloor\times B$ ；
左方大通道： $x=\lfloor\frac{S_x}{B}\rfloor\times B$ ；
右方大通道： $x=\lceil\frac{S_x}{B}\rceil\times B$ 。

同样对终点也找到四个方向最近的大通道。

枚举所有可能的组合：

起点连接到哪个大通道（上下左右 4 种）加上终点连接到哪个大通道上下左右 4 种）一共

4\times 4=16

种情况。

对于每种情况：

计算从起点到大通道的时间（非大通道部分 $\times K$ ）；
计算在大通道上移动的时间（大通道部分 $\times 1$ ）；
计算从大通道到终点的时间（非大通道部分 $\times K$ ）。

特殊情况处理

当起点和终点在同一大通道区域时，dis 函数（见 Code）会特殊处理：

如果两点都在垂直大通道上且在同一水平区域，可以选择直接垂直移动或绕行；
如果两点都在水平大通道上且在同一垂直区域，可以选择直接水平移动或绕行。

dis 函数计算两点在大通道上的最短移动距离，考虑了：

直接移动以及绕行（当两点在同一大通道区域时）。

总体复杂度为

O(16\times T)

。

Code

CPP

int dis(int x1,int y1,int x2,int y2){
    // 两点都在垂直大通道上且在同一水平区域
    if(x1%b==0&&x2%b==0&&y1/b==y2/b)
        return min(abs(x1-x2)+min(y1%b+y2%b,b*2-y1%b-y2%b),abs(y1-y2)+abs(x1-x2)*k);
    // 交换坐标，检查是否都在水平大通道上且在同一垂直区域  
    swap(x1,y1),swap(x2,y2);
    if(x1%b==0&&x2%b==0&&y1/b==y2/b)
        return min(abs(x1-x2)+min(y1%b+y2%b,b*2-y1%b-y2%b),abs(y1-y2)+abs(x1-x2)*k);
    // 一般情况：曼哈顿距离
    return abs(x1-x2)+abs(y1-y2);
}

题解：AT_abc258_f [ABC258F] Main Street

文章操作

前置

题目大意

解题思路

特殊情况处理

Code

相关推荐

评论

题解：AT_abc258_f [ABC258F] Main Street