Zth's Blog

记录学习路上的点滴

0%

环形均分纸牌

经典问题, 均分纸牌和环形均分纸牌

均分纸牌问题

题意

有$n$个人排成一行, 第$i$个人手中有$a_i$张纸牌, 在每一步操作中, 可以让某个人把自己手中的一张纸牌交给他旁边的一个人, 求最少的操作次数使得所有人手中的纸牌数量相同

题解

设$sum = \sum a_i$, 显然如果$sum \% n \neq 0$, 则不可能达到, 我们只考虑$sum \% n = 0$的情况

设$avg = \frac{sum}{n}$, 即最后每个人手中的纸牌数量

我们首先考虑第一个人

  1. $a_1 > avg$, 此时第一个人必须要给第二个人$a_1 - avg$张纸牌, 花费同样的代价, 此时$a_2$变为$a_2 + a_1 - avg$
  2. $a_1 < avg$, 此时第一个人必须要从第二个人手里拿到$avg - a_1$张纸牌, 花费同样的代价, 此时$a_2$变为$a_2 - (avg - a_1)$, 注意如果这里出现了$a_2 < 0$的情况也没有关系, 这时第二个人只需要从第三个人手里拿纸牌就可以了
  3. $a_1 = avg$, 此时不用动

对于$2$到$n$个人, 我们可以重复这样的操作, 实质上就是考虑第$i$个人和第$i + 1$个人之间传递了多少张纸牌

前$i$个人手里的纸牌数量为$\sum_1^i a_i$, 那么显然第$i$个人需要和第$i + 1$个人传递$|\sum_1^i a_i - avg \times i|$张纸牌, 因为这是唯一改变前$i$个人手中纸牌数量和的方式

那么我们的答案就是

这里的上界是$n$或$n + 1$都行

环形均分纸牌问题

题意

在均分纸牌的基础上加上第一个人和第$n$个人相邻的条件, 即$n$个人构成一个环, 其他条件不变

题解

思路1

lyd书上说的是

仔细思考可以发现, 一定存在一种最优解的方案, 环上某两个相邻的人之间没有发生纸牌交换操作。 于是有一种朴素的做法是, 枚举这个没有发生交换的位置, 把环断开看成一行, 转化为一般的“均分纸牌”问题进行计算

下面展示仔细思考:

首先只有两个人的情况不予考虑, 因为没有什么思考价值

我们观察到在最优情况下, 某相邻两个人之间要么不发生传递, 要么只会发生一种方向的传递, 这是显然的

那我们不妨先假设最优结果中, 每相邻两个人之间都发生了至少一次传递

图中箭头代表传递的方向, $x_i$代表相对于初始状态我们传递的纸牌数量

现在假设我们一次顺时针方向的传递(逆时针同理), 每两个相邻的人之间都传递一次, 这个操作显然是无意义的, 并不会改变每个人手中的纸牌数量, 但是他可以转换成另一种操作: 所有顺时针箭头的$x$加$1$, 逆时针箭头的$x$减$1$, 如下图所示

因为我们假设是对最优解做了这个操作, 那么操作完的答案一定和原来的答案是一样的, 否则我们原来的一定不是最优解。 这里简单解释一下, 如果我们操作完答案减小了, 那么原答案就不是最优的; 如果我们操作完答案增加了, 那我们换成逆时针操作, 答案就会减小, 原答案不是最优的

这其实暗示了最优解中两种方向的箭头数量一定是一样的(不过好像没有什么用, 但这和货仓选址的思路有点类似, 找到中点以后左右移动都会使答案变得不更优, 算是提示了我们正解该怎么做吧)

那我们找到最小的$x_i$, 按照它的反方向操作$x_i$次, $x_i$就变成了$0$, 也就是出现了两个相邻的人之间没有发生传递, 而答案和原来是一样的

以上思路其实就是对一般的情况特化到我们要的情况而没有改变答案, 只是简单转化而已

正解思路

方便起见, 我们让$a_i$全都减去$avg$, 变成需要传递出去的纸牌数量, 然后设$s_i = \sum_{i = 1}^i a_i$, 即前缀和

把原来的线性均分纸牌中每个人的初始纸牌数量, 前缀和表示一下

最终答案为

那如果我们现在从第$k$个人后面断开这个环, 再表示一下

注意此时由于我们所有的$a_i$事先减去了$avg$, 所以有$s_n = 0$

也就是说, 从第$k$个人之后断开后表示, 前缀和数组的变换是每个位置都减去$s_k$, 答案变为

然后我们选一个$i$使这个答案最小就可以了对吧

这不就是货仓选址吗, 排序取中位数就好了

当我们无法通过直接分析得到答案时, 不妨写一下式子, 看看能不能通过数学推导简化式子从而发现一些性质解决问题