纸牌均分

有 N 个人排成一排，它们的手中分别有 C[1] ~ C[N] 张纸牌，在每一步操作中，可以让某个人把自己手中的一张纸牌交给他旁边的一个人，求至少需要多少步操作才能让每个人手中持有的纸牌数相等。

首先令 M 为这N 个人的纸牌总数，显然，问题有解，M 能被 N 整除。令avg = M / N，均分完成后每个人都有 avg 张纸牌。

首先考虑第一个人，他只能与第二个人交换纸牌。若C[1] > avg，第一个人需要给第二个人 C[1] - avg 张纸牌；若C[1] < avg，第一个人需要从第二个人手中拿 avg - C[1] 张纸牌。

类似地，考虑第 i 个人和第 i + 1 个人之间的交换。令 $ S[i]=\sum_{k=1}^{i}C[i]$，即数组C的前缀和。若 S[i] < i * avg，那么第 i 个人必须从第 i + 1 个人手中拿走 i * avg - S[i] 张纸牌（否则前 i 个人的纸牌总数不可能为 i * avg，也不可能没人都有 avg 张牌）。同样若S[i] > i * avg，第 i 个人给第 i + 1 个人S[i] - i * avg 张牌。

因此，最少交换次数就是$\sum_{i=1}^N\left|S[i]-\frac{M}{N} \right|$。

环形纸牌均分（糖果传递）

与上题的不同之处在于，N 个人是围成一圈而不是排成一排，因此第一个人和最后一个人之间是可以传递纸牌的。

设第 i 个人给第 i + 1 个人 $x_i$ 张牌（若是第 i + 1 个人给第 i 个人纸牌，$x_i$为负数），特别地，第 N 个人给第1个人$x_N$张纸牌，那么，有以下等式：

转化一下：

而$(c_1+c_2+…+c_i)-i*avg$是已知的常量，令它为$D_i$。

那么我们的问题就成了求下面式子的最小值：

只需要考虑$x_N$取何值即可。这其实就是就是货仓选址问题，我们直接用结论：$x_N$取$D_i(i=1,2,…,N)$的中位数时，上式取最小值。

经过以上的理论分析之后，代码就很容易写了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <cmath>
#include <iostream>
#define LL long long
using namespace std;
int arr[1000001];
int main() {
  int n;
  LL sum = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    sum += arr[i];
  }
  int avg = sum / n;
  for (int i = 0; i < n; i++) {
    arr[i] -= avg;
    if (i > 0) arr[i] += arr[i - 1];
  }
  sort(arr, arr + n);
  int mid = n / 2;
  sum = 0;
  for (int i = 0; i < n; i++) {
    sum += abs(arr[mid] - arr[i]);
  }
  cout << sum << endl;
}

七夕祭

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。

矩形的祭典会场由 N 排 M 列共计 N×M 个摊点组成。

虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。

不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在 Vani 想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

输入格式

第一行包含三个整数 N 和 M 和 T，T 表示 cl 对多少个摊点感兴趣。

接下来 T 行，每行两个整数 x,y，表示 cl 对处在第 x 行第 y 列的摊点感兴趣。

输出格式

首先输出一个字符串。

如果能满足 Vani 的全部两个要求，输出 both；

如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；

如果只能使各列中 cl 感兴趣的摊点数一样多，输出 column；

如果均不能满足，输出 impossible。

如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

数据范围

1≤N,M≤100000,
0≤T≤min(N∗M,100000),
1≤x≤N,
1≤y≤M

输入样例：

1
2
3
4
5
2 3 4
1 3
2 1
2 2
2 3

输出样例：

1
row 1

其实跟环形纸牌均分没啥区别，就是题干有点离谱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#define LL long long
using namespace std;
int t;
LL minChange(vector<int>& arr) {
  int n = arr.size() - 1;
  int tar = t / n;
  for (int i = 1; i <= n; i++) {
    arr[i] -= tar;
  }
  vector<int> sum(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + arr[i];
  }
  sort(sum.begin() + 1, sum.end());
  int ct = (1 + n) / 2;
  LL ret = 0;
  for (int i = 1; i <= n; i++) {
    ret += abs(sum[i] - sum[ct]);
  }
  return ret;
}
int main() {
  int n, m, c, l;
  cin >> n >> m >> t;
  vector<int> row(n + 1, 0);
  vector<int> col(m + 1, 0);
  for (int i = 0; i < t; i++) {
    cin >> c >> l;
    row[c]++;
    col[l]++;
  }
  if (t % n == 0 && t % m == 0) {
    cout << "both " << (minChange(row) + minChange(col));
  } else if (t % n == 0) {
    cout << "row " << minChange(row);
  } else if (t % m == 0) {
    cout << "column " << minChange(col);
  } else {
    cout << "impossible";
  }
  return 0;
}