CF1421D Hexagons（题解）

· · 题解

P.S.

这题的 idea 不是笔者提供的（毕竟笔者这么菜）。
感谢 @zhouchenyuan005 提供的思路，这篇题解的代码比楼上楼下的都短（目前），主要代码就两行。

Discription.

给定一个六边形网格，你每次可以往六个方向运动，每个方向有一个代价。
求从源点运动到指定点至少需要多少的代价。

Solution.

首先，这个六边形看着就很不舒服，那么我们就把它按照题面的坐标强行放到坐标系中去。
然后我们发现题目就转化成了下图：

        Y
        ↑
        |
        |
        |
        c6
        ↑   c1
        | ↗
c5←-----.------→ c2------------→ X
    ↙  |
c4      ↓
        c3

那么我们假设我们要在 x 方向运动 a_2 的距离（向左则为负
要在 y 方向上运动 a_3 的距离，要在斜线方向上运动 a_1 的距离。
那么很显然，我们能得到两个方程。

a_2+a_1=X a_1-a_3=Y

所以，显然地，我们有：

a_2=X-a_1\ ,\ a_3=a_1-Y

而最终的答案就是：

k_1\times a_1+k_2\times a_2+k_3\times a_3

（k_1 k_2 k_3 都是常量，就是可能需要分类讨论 a 的正负性。
于是上面这个函数肯定是关于 a_1 的一次函数。
由于初中所学，一个套上分类讨论系数的一次函数如果有最小值，那么最小值肯定在分类讨论边界取到。
而上面的三个分类讨论边界分别就是 a_1=0 a_2=0 a_3=0
所以我们只需要把 a_1=0,X,Y 时上面的函数取最小值。
三个分别计算一下就好了（请记住你是 OIer 而不是 MOer。

Coding.

//愿你有一天能和你重要的人重逢。
#include<bits/stdc++.h>
using namespace std;int T;long long X,Y,c1,c2,c3,c4,c5,c6;
inline long long calc(int x) {int a1=x,a2=Y-a1,a3=a1-X;return (a1>0?c1:-c4)*a1+(a2>0?c2:-c5)*a2+(a3>0?c3:-c6)*a3;}
int main() {for(scanf("%d",&T);T--;) scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&X,&Y,&c1,&c2,&c3,&c4,&c5,&c6),printf("%lld\n",min(calc(0),min(calc(X),calc(Y))));}