题干

题目传送门

解析

这题还是很考验思维的。看了一些题解用的是贪心解法，我这里不用贪心解法，思维量太大并且要证明的东西太多了。贪心这个东西，大家懂的都懂，证明很难，而一旦证出来这个题很快就能做出来了。

首先，对于每一组数据，记训练前的属性为 $a[i](i=0,1,2)$，训练后的属性为 $b[i](i=0,1,2)$。只要有任何的一个 $a[i]-b[i]$ 不是 $20$ 的倍数，就直接输出-1。如果 $a[0]+a[1]+a[2]\neq b[0]+b[1]+b[2]$，也直接输出-1。否则接着考虑。

我们将给属性 $i$ 提升为 $c_ i$ 的操作记为三元组 $(c_ 1,c_ 2,c_ 3)$。因此题干中的说法，归根结底就是三种操作 $(40,-20,-20),(-20,40,-20),(-20,-20,40)$。操作 $(-40,20,20)$ 可以看作 $-1$ 次操作 $(40,-20,-20)$，你懂我意思吧。记上面三种操作分别执行了 $a,b,c$ 次。

我们不妨记 $x=(b[0]-a[0])/20,y=(b[1]-a[1])/20,z=(b[2]-a[2])/20$。显然我们可以列出方程组：

$$\begin{cases}2a-b-c=x\\2b-a-c=y\\2c-a-b=z\end{cases}\tag 1$$

注意这里 $x,y,z$ 都是常量，题目直接告诉我们的；未知量是 $a,b,c$。

这个方程组想必不用多解释，注意到应有 $x+y+z=0$，因此这个方程组的三个方程是线性相关的，去除冗余之后实际上是两个方程组成的方程组：

$$\begin{cases}2a-b-c=x\\2b-a-c=y\end{cases}\tag 2$$

那么实际上 $a,b,c$ 中有一个是自由变量（因为增广矩阵的秩为 $2$），不妨采用 $b$ 为自由变量，那么我们可以用 $b$ 来表示 $a$ 和 $c$。实际上将方程组 $(2)$ 的两个方程相减，有 $3a-3b=x-y$，也就是

$$a=b+\cfrac{x-y}{3}\tag 3$$

注意到我们的 $a,b,c\in\mathbb Z$，因此 $(x-y)/3$ 也必须是整数，如果不是整数可以直接输出-1了。为了简便，记 $p_1=(x-y)/3$。因此可以用 $b$ 表示 $a$ 为 $a=b+p _ 1$。

至于 $c$，方程组 $(1)$ 中的最后一个方程已经告诉我们

$$c=\cfrac{z+a+b}{2}=\cfrac{z+p_1}{2}+b\tag 4$$

显然这里的 $z+p_1$ 必须是偶数，不然可以直接输出-1了。为了简便，我们记 $p _ 2=(z+p_1)/2$。那么可以用 $b$ 表示 $c$ 为 $c=b+p _ 2$。

题目中要求的最少的次数，实际上就是 $|a|+|b|+|c|=|b+p_1|+|b|+|b+p_2|$。构造如下的函数

$$f(t)=|t|+|t+p_1|+|t+p_2|\tag 5$$

实际上就是求 $\min _ {b\in\mathbb Z}f(b)$。注意到 $f$ 是多个绝对值函数的和，这种函数的特点是没有最大值，且最小值一定在拐点（非数学意义上二阶导为 $0$ 的拐点）处取到。这里有三个拐点，分别是 $0,-p_1,-p_2$。因此我们的答案就是 $\min(f(0),f(-p_1),f(-p_2))$。

心得

本篇题解全文没有用到贪心思维，所有内容均可以使用高中数学内容进行阐述，理解起来非常方便。果然还是要先学好数学再搞算法。

参考代码

这里给一份 C++ 的AC代码。

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
ll a[3],b[3];

int t,ans;

int main() {
    cin >> t;
    while(t--) {
        for(int i = 0;i < 3;i++)
            cin >> a[i];
        for(int i = 0;i < 3;i++)
            cin >> b[i];
        if((a[0] - b[0]) % 20 or (a[1] - b[1]) % 20 or (a[2] - b[2]) % 20 or (a[0] + a[1] + a[2] != b[0] + b[1] + b[2]))
            cout << "-1\n";
        else {
            ll x = (b[0] - a[0]) / 20,y = (b[1] - a[1]) / 20,z = (b[2] - a[2]) / 20;
            if((x - y) % 3) cout << "-1\n";
            else {
                ll p1 = (x - y) / 3;
                if((z + p1) & 1) cout << "-1\n";
                else {
                    ll p2 = (z + p1) >> 1;
                    ll ans = abs(p1) + abs(p2);
                    ans = min(ans,abs(p1) + abs(p2 - p1));
                    ans = min(ans,abs(p2) + abs(p2 - p1));
                    cout << ans << '\n';
                }
            }
        }
    }
    return 0;
}