考虑 “纸牌均分问题” 如何解决?
设一共有 M 个人,每个人初始的纸牌数量为 ci,纸牌总数为 T
显然当 M∤ 时,方案不存在,现只考虑方案存在的情况
第 1 个人为了达到平均持有数,需要向第 2 个人传递 c_1 - T / M 数量的牌(正数是给,负数是拿)
第 2 个人为了达到平均持有数,需要向第 3 个人传递 c_2 - T / M + c_1 - T / M 数量的牌
......
第 n-1 个人为了达到平均持有数,需要向第 n 个人传递 \sum_{i=1}^{n-1} c_i - (n-1) \times T / M 数量的牌
此时前 n-1 人都达到了平均数,则第 n 个人必然也达到了平均数
统计易得,最小交换次数为:
\sum_{i=1}^{n-1} \Big| { \sum_{j = 1}^i (c_j - \frac{T}{M}) } \Big|
不妨设 A_i = c_i - T / M,于是化简可得:
\sum_{i=1}^{n-1} \Big| { \sum_{j=1}^i A_j } \Big| = \sum_{i=1}^{n-1} | { S_i } | \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和,即 } S_i = \sum_{j=1}^i A_j
考虑 “纸牌均分问题” 如何延伸到 “环形纸牌均分问题” ?
环形区间的问题,第一想到的就是 破环成链 了
经过思考发现,一定存在一个最优解方案,环上有相邻的两个人之间没有发生交换
这部分证明如下:
如果环上相邻两人全部发生交换,则会出现两种情形:(正数传递为有向边的正向方向)
- 出现一个环
这种方案肯定不是最优解,因为给出去的纸牌经过一圈收回来了,显然浪费了操作次数
我们在这个环上断开交易数量最小的一条交换边,并使其他边减少该边的交换数量,必然不会使方案变差- 出现一个点到达另一个点有两条路径
我们可以断开起点两条出边中 val = cnt \times w 最小的那一套边,并该边权值累加到另一条路径的每一条边上,其结果不会变差(其中 cnt 是起点到终点路径上经过的点数,w 是这条边的权重)
一个朴素的做法是直接枚举断点的位置,然后做一遍线性纸牌均分,但是时间复杂度为 O(n^2) 不可取,需要推导
现将这 n 个人的 A_i 和 S_i 罗列出来 (A_i = \sum\limits_{j=1}^n (c_j - \dfrac{T}{M}), S_i = \sum\limits_{j = 1}^i A_j)
\begin{matrix} A_1 & S_1 \\\\ A_2 & S_2 \\\\ \cdots & \cdots \\\\ A_k & S_k \\\\ A_{k+1} & S_{k+1} \\\\ \cdots & \cdots \\\\ A_n & S_n \end{matrix}
考虑在第 k 个人之后断开,则环化成链有:
\begin{matrix} A_{k+1} & S_{k+1} - S_k \\\\ \cdots & \cdots \\\\ A_n & S_n - S_k \\\\ A_1 & S_1 + S_n - S_k \\\\ A_2 & S_2 + S_n - S_k \\\\ \cdots & \cdots \\\\ A_k & S_k + S_n - S_k \\\\ \end{matrix}
又易知 S_n = \sum c_j - n \times T / m = 0,故求得最小步数为:
\sum_{i=1}^n |S_i - S_k| \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和,即 } S_i = \sum_{j=1}^i A_j
该绝对值不等式最小值的求解,就同上一题 “货仓选址” 异曲同工了
因此 S_k 的选择,就取 S_i 排序后的中位数即可
第二种推导方式
这种推导方式相较于上一种,思维量小,但对公式的变形要求高,是直接统计每个点
考虑直接在环上求解,环的顺时针方向设为正方向,若边权为正,表示左向右传递;反之则是右向左传递
设 d_i 表示第 i 个人向第 (i+1)\bmod n 传递的所有纸牌数量
传递完成后的结束是所有人的纸牌数量变成平均数,以此建立方程组有:
\begin{cases} avg =& c_1 - d_1 + d_n \\\\ avg =& c_2 - d_2 + d_1 \\\\ \cdots \\\\ avg =& c_{n-1} - d_{n-1} + d_{n-2} \\\\ avg =& c_{n} - d_{n} + d_{n-1} \end{cases} \qquad \Rightarrow \qquad \begin{cases} d_1 &= c_1 - avg + d_n \\\\ d_2 &= c_2 - avg + d_1 \\\\ \cdots \\\\ d_{n-1} &= c_{n-1} - avg + d_{n-2} \\\\ d_n &= c_{n} - avg + d_{n-1} \end{cases}
观察易得,相邻两个等式之间,有可以代入的项,从上到下用滚动相消法可得:
\begin{cases} d_1 =& c_1 - avg + d_n \\\\ d_2 =& \sum\limits_{i=1}^2 c_i - 2 \times avg + d_n \\\\ \cdots \\\\ d_{n-1} =& \sum\limits_{i=1}^{n-1} c_i - (n-1) \times avg + d_n \\\\ d_n =& \sum\limits_{i=1}^{n} c_i - n \times avg + d_n \end{cases}
易得通项:d_i = \sum\limits_{j=1}^{i} c_j - i \times avg + d_n = d_n + \sum\limits_{j=1}^{i} (c_j - avg) = d_n - \sum\limits_{j=1}^{i} (avg - c_j)
不妨设 A_i = avg - c_i, S_i = \sum\limits_{j = 1}^i A_j,则通项可以化简为:d_i = d_n - \sum\limits_{j=1}^{i}A_j
则总共的操作数为:
\sum_{i=1}^n d_i = \sum_{i=1}^n |d_n - \sum_{j=1}^i A_j| = \sum_{i=1}^n |d_n - S_i|
由 绝对值不等式 易得:d_n 应取 S_i 排序后的中位数
long long calc(int c[], int n)
{
int avg = t / n;
for (int i = 1; i <= n; i ++ ) a[i] = c[i] - avg;
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
sort(s + 1, s + n + 1);
long long res = 0;
for (int i = 1; i <= n; i ++ ) res += abs(s[i] - s[(n + 1) / 2]);
return res;
}
Code
#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int n;
int c[N];
LL s[N], a[N];
long long calc(int c[], int n)
{
int avg = accumulate(c + 1, c + n + 1, 0ll) / n;
for (int i = 1; i <= n; i ++ ) a[i] = c[i] - avg;
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
sort(s + 1, s + n + 1);
long long res = 0;
for (int i = 1; i <= n; i ++ ) res += abs(s[i] - s[(n + 1) / 2]);
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);
printf("%lld\n", calc(c, n));
return 0;
}
数学薄纱我
这数学学得太好了
神!%%%%%%
文中A(i)的定义前后有矛盾,有一处应该是笔误了
A(i)=avg-a(i)和a(i)=c(i)-avg是不是对不上呢?
没想到写错也能过呢
是A(i)=avg-a(i)和a(i)=c(i)-avg
NB ,给你点个收藏
我去!牛逼啊!