BZOJ3032 七夕祭【绝对值不等式】【中位数】【数形结合】

显然最后每个人都剩下sum/n张纸牌，p[i]表示这个人给下一个人多少张纸牌

显然p[i]=a[i]+p[i-1]-sum/n

p[i]-p[i-1]=a[i]-sum/n,所以p[i]-p[i-1]+p[i-1]-p[i-2]+.....-p[1] = sigma(i)(a[i]-sum/n)

即p[i]=sigma(i)(a[i]-sum/n)+p[1]

显然sigma(i)(a[i]-sum/n)是定值，所以p[1]是所有sigma(i)(a[i]-sum/n)的中位数就好了

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=a;i<=b;i++)
const int maxn = 100008;
long long n,m,k,a[maxn],b[maxn],c[maxn];
long long num(long long *h,long long x)
{long long now = k/x;_for(i,1,x)c[i]=0;_for(i,1,k)c[h[i]]++;_for(i,1,x)c[i]+=c[i-1]-now;sort(c+1,c+1+x);long long ans = 0;_for(i,1,x)ans+=abs(c[x/2+1]-c[i]);return ans;
}
int main(int argc, char const *argv[])
{scanf("%d%d%d",&n,&m,&k);_for(i,1,k)cin>>a[i]>>b[i];int flag = 0;if(k%n==0&&k%m==0)flag = 1;else if(k%n!=0&&k%m==0)flag = 2;else if(k%n==0&&k%m!=0)flag = 3;else flag = 4;if(flag==4)printf("impossible\n");else if(flag==3)printf("row %ld\n", num(a,n));else if(flag==2)printf("column %ld\n",num(b,m));else printf("both %ld\n",num(a,n)+num(b,m));return 0;
}