算法思路
考虑到本题的实际操作机制，行内相邻交换不会导致列分布变化、列内交换不会导致行分布变化，根据这点我们可以将本题拆分为分别对行和列做循环交换操作。
假设一个环形结构\([a_1, a_2 ... a_n]\)，需要将其中所有的数字通过相邻数字间的交换变为\(a\)，假设从\(a_i \to a_{i + 1}\)传递\(x_i\)个数字(\(x_i\)可正可负，且\(a_n\to a_1\)为\(x_n\))则有
\[a_1 + x_n - x_1 = a \\ a_2 + x_1 - x_2 = a \\ ... \\a_n + x_{n - 1} - x_n = a\]
整理得
\[x_1 - x_n = a_1 - a \\ x_2 - x_1 = a_2 - a \\ ... \\ x_n - x_{n - 1} = a_n - a\]
由于希望求得最小的操作次数，即题目希望求得最小的\(|x_1| + |x_2| + ... +|x_n|\)则有
\[x_1 = x_1 \\ x_2 = x_1 - (a - a_2) \\ x_3 = x_2 - (a - a_3) = x_1 - (2a - a_2 - a_3) \\ ... \\ x_n = x_{n - 1} - (a - a_n) = ... = x_1 - ((n - 1)a-a_2-a_3 ... -a_n)\]
即最终上面的式子被转化为了\(|x_1| + |x_1 - (a-a_2)| ...+|x_1 - [(n - 1)a - a_2 - a_3 ... -a_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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m, t;
int r[N], c[N];
long long compute(int a[], int avg, int cnt)
{
int buf[N];
for (int i = 2; i <= cnt; ++i)
{
buf[i] = avg - a[i] + buf[i - 1];
}
sort(buf + 1, buf + cnt + 1);
int mid = (1 + cnt) >> 1;
long long res = 0;
for (int i = 1; i <= cnt; ++i)
{
res += abs(buf[i] - buf[mid]);
}
return res;
}
int main()
{
cin >> n >> m >> t;
for (int i = 0; i < t; ++i)
{
int x, y;
cin >> x >> y;
r[x] ++;
c[y] ++;
}
int col_res = 0, row_res = 0;
int col_avg = 0, row_avg = 0;
if (t % m && t % n) cout << "impossible";
else if (t % m)
{
cout << "row ";
cout << compute(r, t / n, n);
}
else if (t % n)
{
cout << "column ";
cout << compute(c, t / m, m);
}
else
{
cout << "both ";
cout << compute(r, t / n, n) + compute(c, t / m, m);
}
}
|