题解：AT_abc359_c [ABC359C] Tile Distance 2

· · 题解

前言

第一眼看到题面的图：不难啊，bfs 一下不就好了？

而看到数据范围的我：0 \le sx,sy,tx,ty \le 10^{16} 哦。。。

思路

贪心。

本文题解里：

设答案为 ans。

  1. 先竖着走完起点和终点的 y 轴距离。此时，ans \gets |ty - sy|。

  2. 为了之后方便，我们使 sx 和 tx 变成他们所在的长方形中左面正方形的左下角坐标。

  3. 继上面的操作，我们设 k = |sx - tx| - |sy - ty|，其实就是从起始点走完起点和终点的 y 轴距离的所在地点离终点的 x 轴距离。（可借助这位大佬的题解的图理解一下）

  4. 继上面的操作，如果 k \le 0，那么说明不用再花费额外的消费。否则每走 2 个 x 轴距离就要多消费 1，所以 ans \gets ans + k \div 2。

完结，撒花！

代码

注意一下 long long 就行。

#include <bits/stdc++.h>
using namespace std;
long long sx, sy, ex, ey;
int main() {
    scanf("%lld%lld%lld%lld", &sx, &sy, &ex, &ey);
    long long ans = abs(ey - sy);
    //1
    if (sy % 2 == 0) sx -= abs(sx % 2);
    else sx -= abs((sx + 1) % 2);
    if (ey % 2 == 0) ex -= abs(ex % 2);
    else ex -= abs((ex + 1) % 2);
    //2
    long long k = (abs(ex - sx) - abs(ey - sy));
    //3
    ans += max(0LL, k / 2); //防止 k<=0
    //4
    printf("%lld", ans);
    return 0;
}