[T535983]Pandasun的糖果
以下为题目
PandaSun的糖果
题目背景
idea by wizard
PandaSun超级喜欢糖果,也非常喜欢排列,他有一个糖果阵,在每次取糖果吃的时候,他需要维护糖果阵的整齐。
请你帮PandaSun维护一下,PandaSun会给你糖吃。
题目描述
PandaSun有一个 $n$ 行 $m$ 列的糖果阵,每一次吃糖果,他都会选择 $r$ 行 $c$ 列的糖果吃掉。
从 $1$ 开始,按照行大号顺序给每个人编号,即编号为 $(r−1)⋅m+c
$ 的人最初位于 $(r,c)$。
为了维护每一次糖果阵的整齐,PandaSun会使用递补策略。
比如说PandaSun要吃这个红色糖果,他最后的糖果阵就会变成图三那样。
爱科学的PandaSun想算出他每次吃糖果的贡献值。
贡献值的算法:
贡献值是每个移动的糖移动的曼哈顿距离之和。
如果某一个糖最初在 $(r_0,c_0)$,然后移动到 $(r_1,c_1)$,则曼哈顿距离为 $|r_0−r_1|+|c_0−c_1|$。
输入格式
第一行包含一个整数 $t
( 1≤t≤10^4
)$ - 测试用例数。
每个测试用例的唯一一行包含 4
个整数 $n$
、 $m$
、 $r$
和 $c(1≤r≤n≤10^6
, 1≤c≤m≤10^6
)$,其中 $n$
是行数, $m$
是列数, $(r,c)$
是离开糖最初所在的位置。
输出格式
对于每组数据,直接输出贡献值即可。
样例 #1
样例输入 #1
1 | 4 |
样例输出 #1
1 | 6 |
提示
校正:PandaSun
第一次思考
主打一个跟着题目走,先写哈夫曼距离,然后是从编号到坐标,再从坐标到编号。极其的痛苦,而且还很失败,测试数据都过不了。
但是我一直在写这个,写了一周左右,直接删了,从头来!
第二次思考
优化哈夫曼距离计算
首先,我优化了哈夫曼距离这一段。因为这里糖果移动只存在2种可能:①在一行开头;②不在一行的开头。
对于①,其距离为m,为什么?因为挪动到上一行,其Δx为(m - 1),Δy为1(移动1行)。
对于②,就是1(没有动行,只前进一列)。
优化转换
这个题本身具有一定的迷惑性,它把一维编号与二维坐标混一块了,这就给我了一个错误的信号:必须互相转化。
但是,有了上一步的优化,我们可以不要二维坐标,因为不再需要计算哈夫曼距离,只需要判断当前糖果是否是每一列第一个,换句话说就是编号减1能被m整除,是的话就加m,不是就加1.这里我们甚至用三目运算符都OK!
完了?是,但是这样也会超时
第三次思考
于是我就在想有没有万能公式啊,还真有!
首先,我们先来计算从当前列到前一行了当前列的所有糖果向前移动的“贡献值”
第一步
我们观察可以发现,上述中一行糖果贡献值之和中只有一个是m,剩下的都是1.剩下了多少?m-1个,综上,我们可以知道,每跨一行,贡献值加 2m - 1。
第二步
既然每一行都一样没那不如一步到位,总共动(n - r)行,这应该很容易推到得到,于是我们得到了(n - r)(2m - 1)是从起始位置移动到最后一行同一列所有“贡献值”
第三步
OK呀胜利在望,只剩最后一行剩下的不分离,更简单(m - c)秒了 ,最终得到了(n - r)(2m - 1)+(m - c)这个公式,收工!
以上思路写下来的代码就可以过了,自己动手吧!
真的是纯cout好吗