七夕节因牛郎织女的传说而被扣上了「情 人节」的帽子。于是 TYVJ 今年举办了一次线 下七夕祭。Vani 同学今年成功邀请到了 cl 同 学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。
TYVJ 七夕祭和 11 区的夏祭的形式很像。矩形的祭典会场由 N 排 M 列共计 N×M 个摊 点组成。虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、 棉花糖、射的屋……什么的。Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布 置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。 不过 zhq 告诉 Vani，摊点已经布置完毕了，唯一的调整方式就是交换两个相邻的摊点。两个 摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于 zhq 率领的 TYVJ 开发 小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在 Vani 想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。
第一行包含三个整数 N 和 M 和 T。T 表示 cl 对多少个摊点感兴趣。 接下来 T 行，每行两个整数 x, y，表示 cl 对处在第 x 行第 y 列的摊点感兴趣。
首先输出一个字符串。如果能满足 Vani 的全部两个要求，输出 both；如果通过调整 只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；如果只能使各列中 cl 感兴趣的摊点 数一样多，输出 column；如果均不能满足，输出 impossible。 如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一 个空格隔开。
分行和列，做环上的均分纸牌问题。 用前缀和找出将环切成链的切分点，前缀和的中位数所在位置即为所求。
写的比较丑，见谅…
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; struct node{ int val,pos; }; bool operator < (node a,node b){ return a.val<b.val; } int n,m,t,col[100010],row[100010],ans=0; node prer[100010],prec[100010]; bool column=false,rowb=false;//row行 col列 int main(){ memset(col,0,sizeof(col)); memset(row,0,sizeof(row)); scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=t;i++){ int c,r; scanf("%d%d",&r,&c); col[c]+=1; row[r]+=1; } //for(int i=1;i<=m;i++) prec[i]=prec[i-1]+col[i]; if(t%m==0) column=true; if(t%n==0) rowb=true; if(column&&rowb) printf("both"); else if(column) printf("column"); else if(rowb) printf("row"); else printf("impossible"); if(rowb){ int avg=t/n; prer[0].val=0; for(int i=1;i<=n;i++) { prer[i].val=prer[i-1].val+row[i]; prer[i].pos=i; } sort(prer,prer+n); int k; if(!n%2) k=prer[n/2].pos; else k=prer[(n+1)/2].pos; for(int i=k;i<=k+n-1;i++){ int cur=i%n; if(cur==0) cur=n; int next=(i+1)%n; if(next==0) next=n; int temp=avg-row[cur]; row[cur]+=temp; row[next]-=temp; ans+=abs(temp); } } if(column){ int avg=t/m; prec[0].val=0; for(int i=1;i<=m;i++) { prec[i].val=prec[i-1].val+col[i]; prec[i].pos=i; } sort(prec,prec+n); int k; if(!m%2) k=prer[m/2].pos; else k=prer[(m+1)/2].pos; for(int i=k;i<=k+m-1;i++){ int cur=i%m; if(cur==0) cur=m; int next=(i+1)%m; if(next==0) next=m; int temp=avg-col[cur]; col[cur]+=temp; col[next]-=temp; ans+=abs(temp); } } if(column||rowb) printf(" %d",ans); return 0; }转载于:https://www.cnblogs.com/leotan0321/p/6081412.html
