AcWing

BZOJ3032权限题

题意：矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分t个摊点感兴趣。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。

分析：行与列是可以独立进行互不影响的.以行为例，结合“均分纸牌”的思想，首先如果t不能被n整除，则肯定无法均分.设hang[i]表示初始时第i行感兴趣的摊点的数量，设\(A1[i]=hang[i]-t/n\)，设\(S1[i]\)表示A1的前缀和，则不考虑环形的话，\(ans1=\sum_{i=1}^m|S1[i]|\).但是题目是“环形均分纸牌”，所以我们要在环上找到一个断点使之变成普通的均分纸牌，假设从第k行断开，则\(ans1=\sum_{i=1}^m|S1[i]-S1[k]|\),结合“货仓选址”的思想，这个\(S1[k]\)就是将S1数组sort排序后的中位数.

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=100005;
int hang[N],lie[N];
LL ans1,ans2,A1[N],S1[N],A2[N],S2[N];
int main(){
    int n=read(),m=read(),t=read();
    for(int i=1;i<=t;++i){
        int x=read(),y=read();
        ++hang[x];++lie[y];
    }
    int bj1=1,bj2=1;
    if(t%n)bj1=0;
    else{
        int ave1=t/n;
        for(int i=1;i<=n;++i){
            A1[i]=hang[i]-ave1;
            S1[i]=S1[i-1]+A1[i];
        }
        sort(S1+1,S1+n+1);
        int cnt1;
        if(n&1)cnt1=S1[(n+1)/2];
        else cnt1=S1[n/2];
        for(int i=1;i<=n;++i)
            ans1+=abs(S1[i]-cnt1);
    }
    if(t%m)bj2=0;
    else{
        int ave2=t/m;
        for(int i=1;i<=m;++i){
            A2[i]=lie[i]-ave2;
            S2[i]=S2[i-1]+A2[i];
        }
        sort(S2+1,S2+m+1);
        int cnt2;
        if(m&1)cnt2=S2[(m+1)/2];
        else cnt2=S2[m/2];
        for(int i=1;i<=m;++i)
            ans2+=abs(S2[i]-cnt2);
    }
    if(bj1&&bj2)printf("both %lld\n",ans1+ans2);
    else if(!bj1&&bj2)printf("column %lld\n",ans1+ans2);
    else if(bj1&&!bj2)printf("row %lld\n",ans1+ans2);
    else printf("impossible\n");
    return 0;
}