均分纸牌(luogu1031)糖果传递(luogu2512)七夕会(bzoj3032)三合一题解

题意转换

首先肯定将有摊位的位置和没摊位的位置进行交换才是又贡献的，所以将摊位看作1，实际上就是环状的均分纸牌的问题

性质

其次行和列是可以分开处理的，对于行而言只需上下移动即可，对于列而言只需左右移动，故行列可分开处理

无解

只需判断总摊位数能否被行数或列数整除即可，都可以的话将答案加起来就可以了

均分纸牌

若一个数不足平均数则向右分一个负数，若一个数超过平均数则向右分一个正数，简单的，两个点之间最多只有一次交换（操作无后效性）平均值可以拓展为目标值，即低于目标值向左传负数，高于目标值向右传正数（如本题）

#include<bits/stdc++.h>
using namespace std;
int n,tot,card[109],ans,f=1;
int main ()
{
    cin>>n;
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        cin>>card[i];
        tot+=card[i];
    }
    tot/=n;
    for(i=1;i<=n;i++)
    {
        card[i]-=tot;
    }
    for(i=1;i<n;i++)
    {
        if(card[i]==0) continue;
        else
        {
            ans++;
            card[i+1]+=card[i];
        }
    }
    cout<<ans;
}
//几年前的代码了（丑死了）

糖果传递

两个点之间依旧最多传递一次，且可以传递负数
故ans=sum(abs(x[i])) x[i]为i到i-1之间传递的值（对于i=1时i-1=n）
已知
a[i]-x[i]+x[i+1]==sum[i…i] (sum[l…r]代表从l到r的目标值的和)
则
x2=sum[2…2]-A1+X1
设 C1为a[1]-sum[2…2]
即 Ci=a[1…i]-sum[2….i+1]
Xi=X1-C[i-1]
ans=sum(abs(x[i])=sum(abs(x[1]-c[i-1])
即x[i]为c[0…n-1]的中位数

为什么是中位数？

若不是中位数，向非中位数方向时（即数少的方向）sum会增大（实践出真知）

#include<bits/stdc++.h>
using namespace std;
long long a[1000009],b[1000009];
long long mid,ans,tot,n;
int main ()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],tot+=a[i];
    tot=tot/n;
    for(int i=1;i<=n;i++) b[i]=b[i-1]-a[i]+tot;
    sort(b+1,b+n+1);
    mid=b[n/2];
    for(int i=1;i<=n;i++) ans+=abs(b[i]-mid);
    cout<<ans;
    return 0;  
}

回到正题

既然我们已经知道环形的均分纸牌怎么做和无解怎么判，那就结束了

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int x[N],y[N],s1[N],s2[N];
int main()
{
    int n,m,T;
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1,a,b;i<=T;i++)
    {
        scanf("%d%d",&a,&b);
        x[a]++,y[b]++;
    }
    if(T%m&&T%n)
    {
        printf("impossible\n");
        return 0;
    }
    for(int i=1;i<=n;i++) x[i]-=T/n;
    for(int i=1;i<=m;i++) y[i]-=T/m;
    long long ans=0;
    if(T%n==0)
    {
        for(int i=1;i<=n;i++) s1[i]=s1[i-1]+x[i];
        sort(s1+1,s1+n+1);
        long long k=s1[(n+1)/2];
        for(int i=1;i<=n;i++)
            ans+=abs(k-s1[i]);
    }
    if(T%m==0)
    {
        for(int i=1;i<=m;i++) s2[i]=s2[i-1]+y[i];
        sort(s2+1,s2+m+1);
        long long k=s2[(m+1)/2];
        for(int i=1;i<=m;i++)
            ans+=abs(k-s2[i]);
    }
    if(T%n==0 && T%m==0) printf("both ");
    else if(T%n==0 && T%m!=0) printf("row ");
    else printf("column ");
    printf("%lld\n",ans);
    return 0;
}