题面：
七夕祭
思路：
1、左右交换不影响行，上下交换不影响列，行和列分开讨论
2、参考糖果传递，明白中位数的意义，糖果传递
3、题目可转换为求|x1-c1|+|x1-c2|+|x1-c3|+…+|x1-cn|的最小（分别对行和列） 其中c1=0, c2=A1-ave, c3=a1+a2-2ave（其中ave为每个位置的最终数值（和除以个数）），以此类推。
4、即为求中位数
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std
;
typedef long long ll
;
const int maxn
=1e5+9;
int n
, m
, t
, x
, y
;
int h
[maxn
], l
[maxn
];
int sum
[maxn
], c
[maxn
];
ll
Fun(int a
[], int n
){
for(int i
=1; i
<=n
; i
++)
sum
[i
]=sum
[i
-1]+a
[i
];
if(sum
[n
]%n
)
return -1;
ll ave
=sum
[n
]/n
;
c
[1]=0;
for(int i
=2; i
<=n
; i
++)
c
[i
]=sum
[i
-1]-(i
-1)*ave
;
sort(c
+1, c
+1+n
);
ll step
=0;
ll zd
=c
[(n
+1)/2];
for(int i
=1; i
<=n
; i
++)
step
+=abs(c
[i
]-zd
);
return step
;
}
int main(){
scanf("%d%d%d", &n
, &m
, &t
);
for(int i
=0; i
<t
; i
++){
scanf("%d %d", &x
, &y
);
h
[x
]++;
l
[y
]++;
}
ll nx
=Fun(h
, n
);
ll my
=Fun(l
,m
);
if(nx
!=-1&&my
!=-1)
printf("both %lld", nx
+my
);
else if(nx
!=-1)
printf("row %lld", nx
);
else if(my
!=-1)
printf("column %lld", my
);
else
printf("impossible");
printf("\n");
return 0;
}
