均分纸牌

简要题意

有 $n$ 堆纸牌，纸牌的总数是 $n$ 的倍数，第 $i$ 堆上有 $a_i$ 张纸牌。

每次只可以移动一张牌，在编号为 $1$ 的堆上取的纸牌，只能移到编号为 $2$ 的堆上；在编号为 $N$ 的堆上取的纸牌，只能移到编号为 $N-1$ 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

求最少的移动次数。

算法：贪心 $O(n)$

显然，最终每一堆的张数都会变成纸牌总数的平均值，所以，每一堆冗余的牌一定要分给其它堆。

我们设 $f[i]$ 为第 $i$ 堆纸牌需要向左边传的纸牌数，$avg$ 为纸牌总数的平均值。

则 $f[i] = f[i - 1] + avg - a[i - 1]$，答案就是移动的纸牌总数。

我们将递推式拆开：

$$f[1] = 0$$

$$f[2] = f[1] + avg - a[1] = avg - a[1]$$

$$f[3] = f[2] + avg - a[2] = 2 * avg - (a[1] + a[2])$$

$$\dots$$

$$f[n] = f[n - 1] + avg - a[n - 1] = (n - 1) * avg - (a[1] + \dots + a[n - 1])$$

设 $sum(i) = a[1] + \dots + a[i]$，即 $f[i] = (i - 1) * avg - sum(i - 1)$，所以最后的答案是 $\sum^{n}_{i=1}|f[i]|$。

类似题目

P1031 [NOIP2002 提高组] 均分纸牌

NOIP 2002 的这道题一次可以移动多张纸牌，所以答案数是 $\sum^{n}_{i=1}[f[i] \ne 0]1$。

代码实现（P1031）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, ans, a[N], sum[N], f[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	int avg = sum[n] / n;
	for (int i = 1; i <= n; i ++ ) {
		f[i] = avg * (i - 1) - sum[i - 1];
		if (f[i] != 0) ans ++ ;
	}
	cout << ans << endl;
	return 0;
}

糖果传递（Luogu P2512）

简要题意

有 $n$ 个小朋友坐成一圈，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$。

算法：贪心 + 货仓选址 $O(n \log n)$

环形均分纸牌问题。

我们继续设 $f[i]$ 为第 $i$ 堆纸牌需要向左边传的纸牌数，$avg$ 为纸牌总数的平均值。

• 当 $2 \le i \le n$ 时，$f[i] = f[i - 1] + avg - a[i]$
• 特别的，$f[1] = f[n] + avg - a[n]$

将递推式分解，得：

$$f[2] = f[1] + avg - a[1]$$

$$f[3] = f[2] + avg - a[2] = f[1] - (a[1] + a[2]) + 2 * avg$$

$$f[4] = f[3] + avg - a[3] = f[1] - (a[1] + a[2] + a[3]) + 3 * avg$$

$$...$$

$$f[n] = f[1] - (a[1] + \dots + a[n - 1]) + (n - 1) * avg$$

设 $sum(i)$ 为 $a[1] \sim a[i]$ 的前缀和，$C[i]$ 为 $sum(i) - i * avg$，则上式等价于：

$$f[2] = f[1] - C[1]$$

$$f[3] = f[1] - C[2]$$

$$f[4] = f[1] - C[3]$$

$$...$$

$$f[n] = f[1] - C[n - 1]$$

因此，答案就是：

$$ans = \sum^n_{i=1}|f[1] - C[i]|$$

根据货仓选址，$f[1]$ 取 $C$ 的中位数时答案最优。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1000010;
ll n, sum, a[N], c[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
		sum += a[i];
	}
	ll ps = sum / n, ans = 0;
	for (int i = 1; i <= n; i ++ ) {
		c[i] = c[i - 1] - a[i - 1] + ps;
	}
	sort(c + 1, c + n + 1);
	ll zws = c[n / 2 + 1];
	for (int i = 1; i <= n; i ++ ) {
		ans += abs(zws - c[i]);
	}
	cout << ans << endl;
	return 0;
}

RESTACK（SPOJ 11117）

简要题意

有 $n$ 个干草堆组成一个环，在第 $i$ 个位置有 $A_i$ 个干草堆，可以将任意位置的干草堆向前或向后移动若干个，使第 $i$ 个位置有 $B_i$ 个干草堆，询问最少需要移动多少个干草堆。

算法：贪心 + 货仓选址 $O(n \log n)$

与上题类似，$B$ 数组也可以前缀和处理。

代码实现

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100010;

int n, sum;
int a[N], b[N], f[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i] >> b[i];
		f[i] = f[i - 1] - a[i - 1] + b[i - 1];
	}
	sort(f + 1, f + n + 1);
	ll ans = 0;
	int zws = f[n / 2 + 1];
	for (int i = 1; i <= n; i ++ ) {
		ans += abs(zws - f[i]);
	}
	cout << ans << endl;
	return 0;
}