一个奇妙的建模题。

Description

给出数轴上三个棋子 $a,b,c$，你可以对棋子进行如下操作：

  • 将一个棋子跳到另一个棋子的另一侧，距离不变，而且不能同时跳过两个棋子。

问最少花费多少步能让三个棋子的位置变为 $x,y,z$。

$-10^9\leq a,b,c,x,y,z\leq10^9$。

Solution

看到这个题感觉非常神秘，手玩一下一个点的所有变化可以发现每个状态最多只有三种变化，如果距离两两相同就只有两种。

然后发现其中一种变化相当于是倒退，而如果距离两两相同就没法倒退了。

我们把距离两两相同的状态看作根，这样所有变化就变成了一棵二叉树。

题目要求的就是两个状态在二叉树上的距离。

再深究一下，往根的方向走会让状态的距离之和变小（例如 $a,b,c$ 变成 $b,2b-a,c$），我们有一个很显然的暴力就是对初始状态和结束状态分别走到根，然后看什么时候相交，这是 $O(n)$ 的（$n$ 是值域）。

再观察一下变化树，发现往根的方向走一步相当于对距离执行一次辗转相减，那么我们用辗转相除就可以 $O(\log n)$ 向上跳了。

这样我们已经可以快速跳，并求出深度了，下一步是求 LCA，树剖之类的方法显然不好用，我们二分一下 LCA 就好了，复杂度 $O(\log^2n)$。

Code

typedef long long ll;
typedef unsigned long long ull;

namespace solve
{
    typedef array<ll, 3> arr;
    const int inf = 2e9;

    arr bg, ed;

    void out(const arr &a) { cout << a[0] << " " << a[1] << " " << a[2] << endl; }

    arr jump(arr a, ll d, int &dep)
    {
        arr res = a;
        ll dis1 = a[1] - a[0], dis2 = a[2] - a[1];
        // out(res);
        if (dis1 == dis2)
            return res;
        if (dis1 < dis2)
        {
            int p = min((dis2 - 1) / dis1, d);
            dis2 -= p * dis1, d -= p, dep += p;
            res[1] = res[2] - dis2, res[0] = res[1] - dis1;
        }
        else
        {
            int p = min((dis1 - 1) / dis2, d);
            dis1 -= p * dis2, d -= p, dep += p;
            res[1] = res[0] + dis1, res[2] = res[1] + dis2;
        }
        return d ? jump(res, d, dep) : res;
    }

    void main()
    {
        for (int i = 0; i < 3; i++)
            cin >> bg[i];
        for (int i = 0; i < 3; i++)
            cin >> ed[i];
        sort(bg.begin(), bg.end()), sort(ed.begin(), ed.end());
        int dep1 = 0, dep2 = 0;
        arr rt1 = jump(bg, inf, dep1), rt2 = jump(ed, inf, dep2);
        //cout << dep1 << " " << dep2 << endl;
        if (rt1 != rt2)
        {
            cout << "NO" << endl;
        }
        else
        {
            cout << "YES" << endl;
            if (dep1 < dep2)
                swap(bg, ed), swap(dep1, dep2);
            int dep = 0;
            bg = jump(bg, dep1 - dep2, dep);
            int l = 0, r = inf, ans = 0;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (jump(bg, mid, dep) == jump(ed, mid, dep))
                    r = mid - 1, ans = mid;
                else
                    l = mid + 1;
            }
            cout << dep1 - dep2 + ans * 2 << endl;
        }
    }
}