【算法】七夕祭

题目?

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。

矩形的祭典会场由?N?排?M?列共计?N×M 个摊点组成。

虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。

不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在 Vani 想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

输入格式

第一行包含三个整数?N?和?M?和?T，T?表示 cl 对多少个摊点感兴趣。

接下来?T?行，每行两个整数?x,y，表示 cl 对处在第?x?行第?y?列的摊点感兴趣。

输出格式

首先输出一个字符串。

如果能满足 Vani 的全部两个要求，输出 both；

如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；

如果只能使各列中 cl 感兴趣的摊点数一样多，输出 column；

如果均不能满足，输出 impossible。

如果输出的字符串不是 impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

数据范围

1 ≤ N , M ≤ 100000
0 ≤ T ≤ min(N ? M,100000)
1 ≤ x ≤ N
1 ≤ y ≤ M

输入样例：

2 3 4
1 3
2 1
2 2
2 3

输出样例：

row 1

思路?

由下图可知，行或列移动次数的最小值为：ans = |x1| + |x2| + |x3| + |x4| + ... + |xn-1| + |xn|

设a = (a1 + a2 + a3 + ... + an) / n 为平均值

则

a1 - x1 + x2 = a

a2 - x2 + x3 = a

a3 - x3 + x4 = a

......

an-1 - xn-1 + xn = a

an - xn + x1 = a

?由此可以推出

x1 = x1 - 0

x2 = x1 + a - a1

x3 = x2 + a - a2 = (x1 + a - a1) + a - a2 = x1 - a1 - a2 + 2*a

......

xn-1 = x1 - a1 - a2 - .... - an-2 + (n - 2) * a

xn = x1 - a1- a2 - a3 - ... - an-1 + (n - 1) * a

其中令cx

c1 = 0

c2 = a - a1

c3 = 2*a - a1 - a2

......

c(n-1) = (n - 2) * a - a1 - a2 - a3 - ... - an-2

cn = (n - 1) * a - a1 - a2 - a3 - ... an-2 - an-1

?因此原式为

ans = |x1 - c1| + |x1 - c2| + |x1 - c3| + |x1 - c4| + ... + |x1 - c(n-1)| + |x1 - cn|

原问题就被化为一个很经典的仓库选址问题，当x1 为 c1 ~ cn的中间值的时候ans为最小值。?

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int row[N],col[N],s[N],c[N];

int work(int n,int a[])
{
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];// 行或列的前缀和
    
    if(s[n] % n) return -1;// 如果不能整除，则表示不能每行或每列店铺都相同
    
    int avg = s[n] / n;// 求出平均值
    

    for(int i = 1;i <= n; i ++) c[i] = s[i - 1] - (i - 1) * avg;
    
    sort(c + 1,c + n + 1);// 对c数组进行排序
    int res = 0;
    for(int i = 1; i <= n ; i ++) res += abs(c[i] - c[(n + 1) / 2]);// 由中位数确定最小值
    
    return res;// 返回行或列需要移动的次数
}

int32_t main()
{
    int n,m,cnt;
    cin >> n >> m >> cnt;// 输入场地大小和cl感兴趣的店铺数目
    while(cnt --)// 输入cl感兴趣的店铺地址
    {
        int x,y;
        cin >> x >> y;
        row[x] ++,col[y] ++;
    }
    
    int r = work(n,row);
    int c = work(m,col);
    
    if(r != -1 && c != -1) cout << "both " << r + c;
    else if(r != -1) cout << "row " << r;
    else if(c != -1) cout << "column " << c;
    else cout << "impossible";
    
    return 0;
}

难度：困难

时/空限制：1s / 64MB

总通过数：7881

总尝试数：21897

来源：《算法竞赛进阶指南》

算法标签 排序https://www.acwing.com/problem/search/1/?search_content=%E6%8E%92%E5%BA%8F贪心https://www.acwing.com/problem/search/1/?search_content=%E8%B4%AA%E5%BF%83推公式https://www.acwing.com/problem/search/1/?search_content=%E6%8E%A8%E5%85%AC%E5%BC%8F

---

题目来自：105. 七夕祭 - AcWing题库