bzoj 3032: 七夕祭

和糖果传递差不多。我是不是眼瞎啊,m写成n都看不出来了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
ll r[N],c[N];
int main(){
    int n,m,T;
    ll s1=0,s2=0;
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=T;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        c[y]++;
        r[x]++;
    }
    for(int i=1;i<=n;++i)s1+=r[i];
    for(int i=1;i<=m;++i)s2+=c[i];
    ll ans=0;
    bool o1=0,o2=0;
    if(s1%n==0){
        o1=1;
        s1/=n;
        for(int i=1;i<=n;++i)r[i]=r[i-1]+s1-r[i];
        sort(r+1,r+1+n);
        for(int i=1;i<=n;++i){
            ans+=abs(r[(n+1)/2]-r[i]);
        }
    }
    
    if(s2%m==0){
        o2=1;
        s2/=m;
        for(int i=1;i<=m;++i)c[i]=c[i-1]+s2-c[i];
        sort(c+1,c+1+m);
        for(int i=1;i<=m;++i){
            ans+=abs(c[(m+1)/2]-c[i]);
        }
    }
    if(o1&&o2)printf("both %lld",ans);
    else if(o1&&!o2)printf("row %lld",ans);
    else if(!o1&&o2)printf("column %lld",ans);
    else printf("impossible");
    return 0;
}
View Code
原文地址:https://www.cnblogs.com/Dream-Runner/p/10131977.html