题目大意
有$n * m$的矩阵, 里面放有$cnt$个糖果。
可进行两个操作:
1. 行操作 : 在某一行中 相邻列可 左右互换
2. 列操作 : 在某一列中 相邻行可 上下互换,
求最终达到一个 每行糖果个数相同, 每列糖果个数相同 的状态 所需要的操作数。
分析可知有如下性质
- 在一行中进行左右互换, 相当于某一列拿出一个糖果给另外一相邻列,但对行的状态无任何影响
- 在一列中进行上下互换, 相当于某一行拿出一个糖果给另外一相邻行,但对列的状态无任何影响
可发现操作行于操作列的 这两个状态是独立的。
所以我们可以分别求 操作行的次数$r$ 和 操作列的次数$c$
最终答案$res = min(r + c) = min(r) + min(c)$
先对 行操作 分析
首先我们先分析为了达到行的最终状态 对行操作 做了几次
我们先画一个糖果交换图
因此:为了达到所有行 糖的个数相等的状态,
操作数 $res$ = $|x_1| + |x_2| + |x_3| +..+ |x_n|$
如何求$res$?
首先我们设每行最终状态的 糖果的个数为 $a$, 我们可发现最终$a$肯定是$a_1 + a_2+..+a_n$的平均数
若$\frac{a_1+a_2+..+a_n}{n}$ 除不尽($n$代表行数), 则无论如何也达不到理想状态, 视为无解即可
可以除尽的情况下,
然后我们先根据上面的图可列出如下方程
$$ \left\\{ \begin{aligned} & a_1 - x_1 + x_2 = a\\\ & a_2 - x_2 + x_3 = a \\\ & … \\\\ & a_{n-1} - x_{n-1}+x_n = a\\\ & a_n - x_n + x_1 = a \\\ \end{aligned} \right. $$
从中可知:$n$个未知量只有$(n-1)$个独立方程, 有$1$个自由变量, 代表有多个解, 我们将这个自由变量指定为$x_1$
因此可转化为
$$ \left\\{ \begin{aligned} & x_1 - x_2 = a_1 - a \\\ & x_2 - x_3 = a_2 - a\\\ & … \\\ & x_{n-1} - x_n = a_{n-1}-a \\\ & x_n - x_1 = a_n - a \end{aligned} \right. $$
然后从第一个公式一步步推
$$ \left\\{ \begin{aligned} & x_1 = x_1 - 0 \\\ & x_2 = x_1 - (a_1 - a) \\\ & x_3 = x_1 - (a_1 + a_2 - 2a) \\\ & … \\\ & x_{n-1} = x_1 - (a_1+a_2+..+a_{n-2} - (n-2) * a)\\\ & x_{n} = x_1 - (a_1+a_2+..+a_{n-1} - (n-1) * a) \end{aligned} \right. $$
我们将每个方程中所有的常数 设为c
即对每个方程
$c_1 = 0$
$c_2 = a_1 - a$
$c_3 = a_1 + a_2 - 2a$
…
$c_n = a_1+a_2+..+a_{n-1} - (n-1)a$
所以求的$res$就可以转换为
$res = |x_1| + |x_2| + |x_3| + …+|x_n|$
= $|x_1 - c_1| + |x_1 - c_2| + .. + |x_1 - c_n|$
从而转化为货仓选址问题…
即$x_1$ 取到$c_1、c_2、..、c_n$的中位数既可
最后$res$ 即为答案, 即行的操作数
列操作分析
列操作 因为于 行操作 是独立的, 则同理求 列的$res$即可咯~
最终 $res = res1 + res2$
代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int row[N], col[N], s[N], c[N];
LL work(int n, int a[]){
for(int i = 1; i <= n; i ++)
s[i] = s[i - 1] + a[i];
if(s[n] % n) return -1;
int avg = s[n] / n;
c[1] = 0;
for(int i =2; i <= n; i ++)
c[i] = s[i - 1] - (i - 1) * avg;
sort(c + 1, c + n + 1);
LL res = 0;
for(int i = 1; i <= n; i ++){
res += abs(c[i] - c[(n + 1) / 2]);
}
return res;
}
int main(){
int n, m, cnt;
scanf("%d%d%d", &n, &m, &cnt);
while(cnt --){
int x, y;
scanf("%d%d", &x, &y);
row[x] ++, col[y] ++;
}
LL r = work(n, row);
LL c = work(m, col);
if(r != -1 && c != -1) printf("both %lld\n", r + c);
else if(r != -1){
printf("row %lld\n", r);
}
else if(c != -1){
printf("column %lld\n", c);
}
else printf("impossible\n");
return 0;
}