0502 七夕祭

忘是亡心i 2022-01-21 10:31 216阅读 0赞

题目链接： [http://contest-hunter.org:83/contest/0x00「基本算法」例题/0502 七夕祭][http_contest-hunter.org_83_contest_0x00_0502]

这个题目用到的数学知识是真的多。  
第一，我们首先可以明确一点就是行和列之间的交换是互不影响的（即：将换两行之间的摊点数是不会影响列的）。所以我们可以行和列分开操作。

第二，从行考虑，想一下每行都有一些摊点数量。现在我想要每一行的摊点数量相同。这是一个什么问题？ 没错就是 摊分纸牌。所以我们可以把摊分纸牌的思想用上来。 但是有一个问题就是摊分纸牌是直线的。可是这个题目是一个环形的（第一行与最后一行相邻）。很明显我们可以枚举哪一个位置是断点就可以了。可是这样太暴力了。所以需要用到前缀和 中位数。这点在算法竞赛进阶指南上有明确的解释。

#include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    ll N,M,T;
    ll row[100100],col[100100],sumr[100100],sumc[100100];
    ll ar[100100],ac[100100];
    
    int main()
    {
        ll markr = 0,markc = 0;
        ll cntr,cntc;
        scanf("%lld%lld%lld",&N,&M,&T);
        for(int i = 1; i <= T; i ++)
        {
            ll x,y; scanf("%lld%lld",&x,&y);
            row[x] ++;
            col[y] ++;
        }
        if(T % N == 0)//先判断能否平分
        {
            ll ave = T / N;
            for(int i = 1; i <= N; i ++)
                sumr[i] = sumr[i - 1] + (row[i] - ave);
            sort(sumr + 1,sumr + 1 + N);
            int mid;
            if(N % 2 == 1)
                mid = (N + 1)/ 2;
            else
                mid = N / 2;
            cntr = 0;
            for(int i = 1; i <= N; i ++)
                cntr += (ll)abs(sumr[i] - sumr[mid]);
            markr = 1;
        }
        if(T % M == 0)
        {
            ll ave = T / M;
            for(int i = 1; i <= M; i ++)
                sumc[i] = sumc[i - 1] + (col[i] - ave);
            sort(sumc + 1,sumc + 1 + M);
            int mid;
            if(M % 2 == 1)
                mid = (M + 1) / 2;
            else
                mid = M / 2;
            cntc  = 0;
            for(int i = 1; i <= M ;i ++)
                cntc += (ll)abs(sumc[i] - sumc[mid]);
            markc = 1;
        }
        if(markc == 1 && markr == 1)
           printf("both %lld\n",cntc + cntr);
        else
            if(markc == 1)
               printf("column %lld\n",cntc);
            else
                if(markr == 1)
                   printf("row %lld\n",cntr);
                else
                   printf("impossible\n");
    }

[http_contest-hunter.org_83_contest_0x00_0502]: http://contest-hunter.org:83/contest/0x00%E3%80%8C%E5%9F%BA%E6%9C%AC%E7%AE%97%E6%B3%95%E3%80%8D%E4%BE%8B%E9%A2%98/0502%20%E4%B8%83%E5%A4%95%E7%A5%AD