七夕祭
题目链接
解析:
- 如果交换左右两边的位置每一行感兴趣的摊位数量不变
同理交换上下两边的位置每一列感兴趣的摊位数量不变
所以该问题可以分解为两个一维的问题：- 用最少的步数使每一行的摊位数目相等
- 用最少的步数使每一列的摊位数目相等
- 前提是总的行数上的感兴趣的数目或总的列数上感兴趣的摊位数目可以被均分
- 接下来解决两个相似的一维问题即可
这和均分纸牌问题相似：M个人拍成一行，每个人手中有C[1]~C[M]张纸牌，每个人都想要拿到相同数量的纸牌，可以让某个人将自己手中的一张牌交给身边的一个人,问最少需要多少次交换。这里假设均分纸牌问题有解：
考虑第一个人：- 若C[1] > avg, 则他需要将C[1] - avg张牌交给第二个人
- 若C[1] < avg, 则他需要从第二个人那里拿avg - C[1]张牌
接下来以此考虑2~M个人。所需最小步数即为 \(\sum_{i=1}^M abs(i*avg-G[i])\) ，其中G[i]=\(\sum_{i=1}^MC[i]\)
其含义是每个“前缀“持有者最初共有G[i]张牌，最终会共有i*avg张牌，设A[i]=C[i]-avg,即从一开始就减掉avg最终每个人只有0张牌
3.但是这个问题可以将头尾互换相当于“环形均分纸牌”，该问题一定有最优解，并且所求的答案可以看作是将环从某一点k断开，其持有的纸牌数，前缀和分别是
A[k+1] S[k+1]-S[k]
A[k+2] S[k+2]-S[k]
…… ……
A[M] S[M]-S[k]
A[1] S[1]+S[M]-S[k]
…… ……
A[k] S[k]+S[M]-S[k]
经推导S[M]一定为0所需最小步数为\(\sum_{i=k+1}^M abs(S[k]-S[i])\) S[i]=\(\sum_{j=1}^iA[j]\) 步数最小时上述公式又转为货舱选址问题，选择中位数即可
代码如下：
// Problem: 七夕祭
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/107/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<stack>
#include<vector>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long LL;
const int N=1e5+10;
int n,m,t;
LL lx[N],ly[N],f[N];
LL handle(LL arr[],int n){
for(int i=1;i<=n;i++) f[i]=f[i-1]+arr[i]-arr[0]/n;
sort(f+1,f+1+n);
int loc=(n+1)>>1;
LL res=0;
for(int i=1;i<=n;i++){
res+=abs(f[i]-f[loc]);
}
return res;
}
int main(){
cin>>n>>m>>t;
while(t--){
int x,y;
cin>>x>>y;
lx[x]++,ly[y]++;
}
for(int i=1;i<=n;i++) lx[0]+=lx[i];
for(int i=1;i<=m;i++) ly[0]+=ly[i];
if(lx[0]%n==0&&ly[0]%m==0) printf("both %lld\n",handle(lx,n)+handle(ly,m));
else if(lx[0]%n==0) printf("row %lld\n",handle(lx,n));
else if(ly[0]%m==0) printf("column %lld\n",handle(ly,m));
else printf("impossible\n");
return 0;
}