2021 RoboCom 世界机器人开发者大赛-本科组（复赛）解题报告 | 珂学家
前言
题解
2021 RoboCom 世界机器人开发者大赛-本科组（复赛）解题报告
感觉这个T1特别有意思，非典型题，着重推演下结论。
7-1 冒险者分队
分值： 20分
思路：解方程组 + 中位数定律
题意省流：
三个数a, b, c 通过如下操作变为 d, e, f
- 选择某个数+40，其余两数-20
- 选择某个数-40，其余两数+20
求最小的操作步骤数，如不存在则返回-1
这类贪心题挺难，如何证明，以及写对挺难得。
前置论点:
- 某个数不可能同时存在+40，又-40的操作，因为两两抵消属于无用功，要满足最小步骤，必然只有一个操作方向
- a + b + c = d + e + f
令x1，x2，x3分别为a,b,c对应40的操作次数,(x1,x2,x3∈Z){令x_1，x_2，x_3分别为a, b, c 对应40的操作次数, (x_1, x_2, x_3 \in Z) }令x1，x2，x3分别为a,b,c对应40的操作次数,(x1,x2,x3∈Z)
- 若xk>0,说明+40操作xk次{若 x_k > 0, 说明 +40操作 x_k次}若xk>0,说明+40操作xk次
- 若xk<0,说明−40操作∣xk∣次{若 x_k < 0, 说明 -40操作 |x_k|次}若xk<0,说明−40操作∣xk∣次
构建对应的三元一次方程组,
{40x1−20x2−20x3=d−a=y1−20x1+40x2−20x3=e−b=y2−20x1−20x2+40x3=f−c=y3\left\{\begin{matrix} 40x_1 - 20x_2 - 20x_3 = d - a = y_1\\ -20x_1 + 40x_2 - 20x_3 = e - b = y_2\\ -20x_1 - 20x_2 + 40x_3 = f - c = y_3 \end{matrix}\right. ⎩⎨⎧40x1−20x2−20x3=d−a=y1−20x1+40x2−20x3=e−b=y2−20x1−20x2+40x3=f−c=y3
求f(x1,x2,x3)=∣x1∣+∣x2∣+∣x3∣最小 求 f(x_1, x_2, x_3) = |x_1| + |x_2| + |x_3| 最小 求f(x1,x2,x3)=∣x1∣+∣x2∣+∣x3∣最小
该方程组的秩为2，没法解, 但是可以把x1,x2表示为x3的形态x_1, x_2表示为x_3的形态x1,x2表示为x3的形态
方程组进行变换为，可求得
{x1=(2y1+y2)/60+x3x2=(2y2+y1)/60+x3\left\{\begin{matrix} x_1 = (2y_1 + y_2) / 60 + x_3 \\ x_2 = (2y_2+y_1) / 60 + x_3 \end{matrix}\right. {x1=(2y1+y2)/60+x3x2=(2y2+y1)/60+x3
进而
f(x1,x2,x3)=∣x1∣+∣x2∣+∣x3∣f(x_1,x_2, x_3) = |x_1| + |x_2| + |x_3| f(x1,x2,x3)=∣x1∣+∣x2∣+∣x3∣
⇒f(x1,x2,x3)=∣x3+(2y1+y2)/60∣+∣x3+(2y2+y1)/60∣+∣x3∣\Rightarrow f(x_1,x_2, x_3) = |x_3+(2y_1 + y_2) / 60| + |x_3 + (2y_2+y_1) / 60| + |x_3| ⇒f(x1,x2,x3)=∣x3+(2y1+y2)/60∣+∣x3+(2y2+y1)/60∣+∣x3∣
⇒f(x1,x2,x3)=∣x3−z1∣+∣x3−z2∣+∣x3−z3∣\Rightarrow f(x_1,x_2, x_3) = |x_3- z_1| + |x_3 - z_2| + |x_3 - z_3| ⇒f(x1,x2,x3)=∣x3−z1∣+∣x3−z2∣+∣x3−z3∣
求这个得最小值，不就是 中位数定律 吗？
取 z1=−(2y1+y2)/60,z2=−(2y2+y1)/60,z3=0三个数的中间值，带入f(x1,x2,x3)即可{ z_1=-(2y_1 + y_2) / 60 , z_2=-(2y_2+y_1) / 60, z_3=0 } 三个数的中间值，带入f(x_1, x_2, x_3) 即可z1=−(2y1+y2)/60,z2=−(2y2+y1)/60,z3=0三个数的中间值，带入f(x1,x2,x3)即可
当然这边的额外条件是
保证 −(2y1+y2)/60,−(2y2+y1)/60-(2y_1 + y_2) / 60 , -(2y_2+y_1) / 60−(2y1+y2)/60,−(2y2+y1)/60 需为整数
#include <bits/stdc++.h>using namespace std;int64_t median(int64_t a, int64_t b, int64_t c, int64_t x) {return abs(x - a) + abs(x - b) + abs(x - c);
}int main() {int t;cin >> t;while (t-- > 0) {int64_t a, b, c;int64_t d, e, f;cin >> a >> b >> c;cin >> d >> e >> f;if (a + b + c != d + e + f) {cout << -1 << "\n";continue;}int64_t y1 = d - a;int64_t y2 = e - b;if ((2*y1 + y2) % 60 != 0 || (2 * y2 + y1) % 60 != 0) {cout << -1 << "\n";continue;}// 方程组求解int64_t z1 = (2 * y1 + y2) / 60;int64_t z2 = (2 * y2 + y1) / 60;vector<int64_t> tmp = {-z1, -z2, 0};sort(tmp.begin(), tmp.end());// 中位数定律int64_t res = median(-z1, -z2, 0, tmp[1]); // tmp[1]为中点cout << res << "\n";}return 0;
}
写在最后
