《算法竞赛进阶指南》0x05排序 环形均分纸牌问题

题目链接：https://www.acwing.com/problem/content/description/107/

其中涉及前缀和和排序以及中位数三种基本思想。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,t;
const int maxn = 100010;
int x[maxn],y[maxn];
int a[maxn],s[maxn];//行信息以及前缀和
int main(){
    cin>>n>>m>>t;
    for(int i=1;i<=t;i++)
        scanf("%d%d",&x[i],&y[i]);
    bool row=!(t%n),column=!(t%m);
    if(row){
        if(column)cout<<"both"<<" ";
        else cout<<"row"<<" ";
    }else if(column){
        cout<<"column"<<" ";
    }else{
        cout<<"impossible"<<endl;
        return 0;
    }
    ll ans=0;
    if(row){//按照均分纸牌的操作对行列分别进行操作
        int num=t/n;
        memset(a,0,sizeof(a));
        for(int i=1;i<=t;i++)a[x[i]]++;
        for(int i=1;i<=n;i++)a[i]-=num;
        for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
        sort(s+1,s+n+1);
        for(int i=1;i<=n/2;i++)ans+=s[n-i+1]-s[i];
    }
    if(column){//按照均分纸牌的操作对行列分别进行操作
        int num=t/m;
        memset(a,0,sizeof(a));
        memset(s,0,sizeof(s));
        for(int i=1;i<=t;i++)a[y[i]]++;
        for(int i=1;i<=m;i++)a[i]-=num;
        for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
        sort(s+1,s+m+1);
        for(int i=1;i<=m/2;i++)ans+=s[m-i+1]-s[i];
    }
    cout<<ans<<endl;
}