【BZOJ 3032】七夕祭

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=3032

【算法】

交换左右两个相邻格子的摊点，不会改变这一行的摊点个数

交换上下两个相邻格子的摊点，不会改变这一列的摊点个数

因此，题目中所要求的两个问题是独立的，可以分别计算，以第一问：每列摊点个数相等，进行讨论：

我们将每列中的初始摊点个数记为Ai，如果感兴趣的摊点总数不能被M整除，则无解，否则，等价于一个“环形均分纸牌”的问题，

如果不允许“环形传递”，那么最少移动步数为 sigma( | Si | ),Si为Ai - T / M的前缀和

如果允许，仔细思考后会发现，一定有一种最优解的方案，使得环上两个人不进行传递，考虑将环断开：

假设断开位置为k，那么断开后，每个人的纸牌个数和前缀和分别为 :

Ak+1 Sk+1 - Sk

Ak+2 Sk+2 - Sk

...

Am Sm - Sk

A1 S1 + Sm - Sk

...

Ak Sk + Sm - Sk

因为Sm = 0，所以，前缀和数组与一般情况的差别就是每个位置都减了Sk

所以若断开位置为k，最少交换次数为： sigma( | Si - Sk| ) , 当Sk取前缀和数组S的中位数时，这个式子的值最小，也就是说，我们将S数组从小到大排序，取中位数Sk就是最优解

那么，这道题就迎刃而解了！

【代码】

#include<bits/stdc++.h>

using namespace std;

#define MAXN 100010

struct pos

{

        int x,y;

} a[MAXN];

int i,N,M,T;

long long ans;

long long s[MAXN];

inline void solve1()

{

        int i;

        memset(s,,sizeof(s));

        for (i = ; i <= T; i++) s[a[i].y]++;

        for (i = ; i <= M; i++) s[i] -= T / M;

        for (i = ; i <= M; i++) s[i] += s[i-];

        sort(s+,s+M+);

        for (i = ; i <= M; i++) ans += abs(s[i] - s[(M+)>>]);

}

inline void solve2()

{

        int i;

        memset(s,,sizeof(s));

        for (i = ; i <= T; i++) s[a[i].x]++;

        for (i = ; i <= N; i++) s[i] -= T / N;

        for (i = ; i <= N; i++) s[i] += s[i-];

        sort(s+,s+N+);

        for (i = ; i <= N; i++) ans += abs(s[i] - s[(N+)>>]);

}

int main()

{

        scanf("%d%d%d",&N,&M,&T);

        for (i = ; i <= T; i++) scanf("%d%d",&a[i].x,&a[i].y);

        if (T % N !=  && T % M != )

        {

                printf("impossible");

                return ;

        }

        if (T % M ==  && T % N != )

        {

                printf("column ");

                solve1();

        } else if (T % M !=  && T % N == )

        {

                printf("row ");

                solve2();

        } else

        {

                printf("both ");

                solve1();

                solve2();

        }

        printf("%lld\n",ans);

        return ;

}

巴特西

【BZOJ 3032】七夕祭

最新文章

热门文章

巴特西

【BZOJ 3032】 七夕祭

最新文章

热门文章

【BZOJ 3032】七夕祭