2019-08-19 17:00 已编辑 C++

关注

七夕祭（算法竞赛进阶指南 P29，中位数 + 思维？）

一.题目链接：

七夕祭

二.题目大意：

中文题不解释.

三.分析：

{

根据移动规则易得：

上下交换两个点，该列中所需摊位个数不变.

左右交换两个点，该行中所需摊位个数不变.

那不妨先上下移动实现 row ，再左右移动实现 col.

立即推：若 t 为 n 的倍数，则可实现 row；若 t 为 m 的倍数，则可实现 col.

下面只讨论如何实现 row，col 类比即可.

{

根据题目描述可得，这是要进行行的部分交换，使得每行的元素个数均相等.

不过这是个环形，为了简化问题，我们先考察线型的问题.

{

即：有一行元素，每个相邻的元素进行部分交换，最终使得每个元素相同.

这个问题很简单，只需要 "多退少补" 到下一个元素即可.

例如：设每个元素的个数为 a[i]，平均数为 mean.

那么可由贪心解决

若 a[1] > mean，则第一个人将 a[1] - mean 个给第二个人.

若 a[1] < mean，则第一个人从第二个人那里取走 a[1] - mean 个.

即：使第一个人达到目标的最少交换次数为 |a[1] - mean|.

同理，对 [2, n] 进行相同操作.

由于第一步只是[1，2]之间的元素交换，所以 sum[2]（前缀和）不变.

所以第二步所需的交换次数为 |2 * mean - sum[2]|

到这里我们可以发现，总共的交换次数为

现在我们对这个式子变形

设

则交换次数为

我们可以注意到：s[n] == 0 是恒成立的（因为元素总数是不变的）.

}

现在我们再来讨论环形的情况.

根据线型，我们知道必定存在一个数 k，使得第 k 行不需要与第 k % n + 1 行进行元素交换.

把环断开，这样问题就转换为了线型问题.

即对于一个数 k：

序列前缀和

A[k + 1] s[k + 1] - s[k]

A[k + 2] s[k + 2] - s[k]

............ .....................

A[n] s[n] - s[k]

A[1] s[1] + s[n] - s[k]

A[2] s[2] + s[n] - s[k]

............ .....................

A[k] s[k] + s[n] - s[k]

又因为 s[n] == 0

所以：

序列前缀和

A[k + 1] s[k + 1] - s[k]

A[k + 2] s[k + 2] - s[k]

............ .....................

A[n] s[n] - s[k]

A[1] s[1] - s[k]

A[2] s[2] - s[k]

............ .....................

A[k] s[k] - s[k]

即：求一个数 k，使得最大.

}

我们把序列 s 排序，即求一个数 k，使得第 k 个位置的点与其他点的距离和最小.

假设第 k 个点左边有 p 个点，右边有 q 个点.

若 k 向右移动一个点，则左边的点距离都加 1，右边的点的距离都减 1，距离和减少了 q - p.

若 k 向左移动一个点，则左边的点距离都减 1，右边的点的距离都加 1，距离和减少了 p - q.

由此可得，k 应选取中位数.

}

四.代码实现：

#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long int
using namespace std;

const int M = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;

struct node
{
    int x, y;
} s[M + 5];

int row_cnt[M + 5];
int col_cnt[M + 5];
int row_sum[M + 5];
int col_sum[M + 5];

int main()
{
    int n, m, t;
    scanf("%d %d %d", &n, &m, &t);
    memset(row_cnt, 0, sizeof(row_cnt));
    memset(col_cnt, 0, sizeof(col_cnt));
    for(int i = 1; i <= t; ++i)
    {
        scanf("%d %d", &s[i].x, &s[i].y);
        row_cnt[s[i].x]++;
        col_cnt[s[i].y]++;
    }
    bool row_flag = !(t % n);
    bool col_flag = !(t % m);
    if(!row_flag && !col_flag)
        printf("impossible\n");
    else
    {
        ll row_change = 0;
        ll col_change = 0;
        if(row_flag)
        {
            int mean = t / n;
            for(int i = 1; i <= n; ++i)
            {
                row_cnt[i] -= mean;
                row_sum[i] = row_sum[i - 1] + row_cnt[i];
            }
            sort(row_sum + 1, row_sum + n + 1);
            int pos = n / 2 + 1;
            for(int i = 1; i <= n; ++i)
                row_change += (ll)abs(row_sum[i] - row_sum[pos]);
        }
        if(col_flag)
        {
            int mean = t / m;
            for(int i = 1; i <= m; ++i)
            {
                col_cnt[i] -= mean;
                col_sum[i] = col_sum[i - 1] + col_cnt[i];
            }
            sort(col_sum + 1, col_sum + m + 1);
            int pos = m / 2 + 1;
            for(int i = 1; i <= m; ++i)
                col_change += (ll)abs(col_sum[i] - col_sum[pos]);
        }
        if(row_flag && !col_flag)
            printf("row %lld\n", row_change);
        else if(!row_flag && col_flag)
            printf("column %lld\n", col_change);
        else if(row_flag && col_flag)
            printf("both %lld\n", row_change + col_change);
    }
    return 0;
}