『アルゴリズムコンテスト進級ガイド』七夕まつり

リンク:http://exam.upc.edu.cn/problem.php?cid=1430&pid=12
件名:
n*m行列におけるT個の点の座標を与え,隣接する座標を移動させることにより,各行(各列)が持つ点数を等しくできるか否かを判断し,最小移動ステップ数を出力する.
第1とnも隣接していると見なす.
考え方:
下のキャンディ転送リンクを参照してください.
関連する問題:キャンディは問題を伝達して、n人の学友
参考:
https://www.cnblogs.com/CtrlCV/p/5626194.html
https://blog.csdn.net/moep0/article/details/52506765
コード:

#include 
#define LL long long
using namespace std;
const int maxn = 1e5+5;

LL t, n, m, x[maxn], y[maxn], s1[maxn], s2[maxn];
void solve()
{
    LL ans = 0, sum = 0;
    if(t%n==0){
        for(int i=1; i<=n; ++i) sum += x[i];
        int average = sum/n;
        for(int i=1; i<=n; ++i) x[i] -= average;
        for(int i=1; i<=n; ++i) s1[i] = s1[i-1]+x[i];
        sort(s1+1, s1+n+1);
        average = s1[(n+1)/2];
        for(int i=1; i<=n; ++i) ans += abs(average-s1[i]);
    }
    sum = 0;
    if(t%m==0){
        for(int i=1; i<=m; ++i) sum += y[i];
        int average = sum/m;
        for(int i=1; i<=m; ++i) y[i] -= average;
        for(int i=1; i<=m; ++i) s2[i] = s2[i-1]+y[i];
        sort(s2+1, s2+m+1);
        average = s2[(m+1)/2];
        for(int i=1; i<=m; ++i) ans += abs(average-s2[i]);
    }
    printf("%lld
", ans);
}
int main()
{
    int a, b;
    scanf("%lld%lld%lld", &n, &m, &t);
    for(int i=1; i<=t; ++i)
        scanf("%d%d", &a, &b), x[a]++, y[b]++;
    if(t%n!=0&&t%m!=0){
        printf("impossible
");
        return 0;
    }
    if(t%n==0&&t%m==0) printf("both ");
    else if(t%n==0) printf("row ");
    else if(t%m==0) printf("column ");
    solve();
}
/***
2 8 8
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
*/