|
|
|
|
|
##[$AcWing$ $105$ 七夕祭](https://www.acwing.com/problem/content/description/107/)
|
|
|
|
|
|
|
|
|
|
|
|
**前序题单**
|
|
|
|
|
|
|
|
|
|
|
|
**[$AcWing$ $104$. 货仓选址](https://www.cnblogs.com/littlehb/p/15459501.html)**
|
|
|
|
|
|
|
|
|
|
|
|
**[$AcWing$ $122$ 糖果传递](https://www.cnblogs.com/littlehb/p/16437042.html)**
|
|
|
|
|
|
|
|
|
|
|
|
**[第$13$届蓝桥杯青少年组$C++$第$5$题 金箍棒 ](https://www.cnblogs.com/littlehb/p/17137629.html)**
|
|
|
|
|
|
|
|
|
|
|
|
### 一、题目描述
|
|
|
|
|
|
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
|
|
|
|
|
|
|
|
|
|
|
|
于是 $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$
|
|
|
|
|
|
|
|
|
|
|
|
**输入样例**：
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
2 3 4
|
|
|
|
|
|
1 3
|
|
|
|
|
|
2 1
|
|
|
|
|
|
2 2
|
|
|
|
|
|
2 3
|
|
|
|
|
|
```
|
|
|
|
|
|
**输出样例：**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
row 1
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 二、问题分析
|
|
|
|
|
|
解法涉及一个贪心模板 ，请先看透这个题 :**[糖果传递](https://www.cnblogs.com/littlehb/p/16437042.html)**
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
首先提醒一下，在一行中，各列摊位之间交换位置，是不改变行的摊位数量的,列同理。
|
|
|
|
|
|
|
|
|
|
|
|
模拟一下交换的过程：
|
|
|
|
|
|
|
|
|
|
|
|
假设七夕祭有$12$个摊位，图中有红圈的是题目主角喜欢的摊位。
|
|
|
|
|
|
|
|
|
|
|
|
经过两轮交换后各列的摊位的红圈的数量都一样了，但各行的红圈数量没有发生过变化。
|
|
|
|
|
|
|
|
|
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2022/07/02/64630_f4288607f9-006eb5E0gy1gcj8m14efqj30x709s3yx.jpg'></center>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
这个题和 **糖果传递** 那个题有什么关联呢？
|
|
|
|
|
|
|
|
|
|
|
|
别急，我先把这个图改一改（把线擦去了）。
|
|
|
|
|
|
<center><img src='https://cdn.acwing.com/media/article/image/2022/07/02/64630_f7bdb50ef9-006eb5E0gy1gcj8qvp4kej30xd09ft95.jpg'></center>
|
|
|
|
|
|
|
|
|
|
|
|
你们看，这些红圈像不像糖果，哈哈哈哈哈哈哈哈，相邻列之间交换摊位，就像是相邻两个小朋友正交换糖果嘛。
|
|
|
|
|
|
|
|
|
|
|
|
**算法思路**：
|
|
|
|
|
|
因为行之间的交换苹果，并不影响列；列之间交换苹果，并不影响行，现在我们想求的是
|
|
|
|
|
|
$$\large min(行变更次数+列变更次数)$$
|
|
|
|
|
|
|
|
|
|
|
|
而行变更与列变更是个自独立的，我们就可以先计算行变更最小值，再计算列变更最小值，加在一起就是答案。
|
|
|
|
|
|
|
|
|
|
|
|
**总结：就是一个两遍糖果传递**
|
|
|
|
|
|
|
|
|
|
|
|
### 三、实现代码
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
|
|
|
|
|
|
typedef long long LL;
|
|
|
|
|
|
|
|
|
|
|
|
const int N = 100010;
|
|
|
|
|
|
|
|
|
|
|
|
int row[N], col[N], s[N], c[N];
|
|
|
|
|
|
|
|
|
|
|
|
LL solve(int n, int a[]) {
|
|
|
|
|
|
int sum = 0;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) sum += a[i];
|
|
|
|
|
|
// 不能整除，最终无法完成平均工作
|
|
|
|
|
|
if (sum % n) return -1;
|
|
|
|
|
|
// 平均数
|
|
|
|
|
|
int avg = sum / n;
|
|
|
|
|
|
|
|
|
|
|
|
// 构建c数组
|
|
|
|
|
|
for (int i = 1; i <= n; i++) c[i] = c[i - 1] + a[i] - avg;
|
|
|
|
|
|
// 排序，为求中位数做准备
|
|
|
|
|
|
sort(c + 1, c + n + 1);
|
|
|
|
|
|
// 计算每个c[i]与中位数的差,注意下标从1开始时的写法 c[(n+1)/2]
|
|
|
|
|
|
LL res = 0;
|
|
|
|
|
|
for (int i = 1; i <= n; i++) res += abs(c[i] - c[(n + 1) / 2]);
|
|
|
|
|
|
|
|
|
|
|
|
return res;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int n, m, T; // n行,m列，对T个摊点感兴趣
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
// 加快读入
|
|
|
|
|
|
ios::sync_with_stdio(false), cin.tie(0);
|
|
|
|
|
|
cin >> n >> m >> T;
|
|
|
|
|
|
while (T--) {
|
|
|
|
|
|
int x, y;
|
|
|
|
|
|
cin >> x >> y;
|
|
|
|
|
|
row[x]++, col[y]++; // x行感兴趣的摊点数+1,y列感兴趣的摊点数+1
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
LL r = solve(n, row), c = solve(m, col);
|
|
|
|
|
|
|
|
|
|
|
|
if (~r && ~c)
|
|
|
|
|
|
printf("both %lld\n", r + c);
|
|
|
|
|
|
else if (~r)
|
|
|
|
|
|
printf("row %lld\n", r);
|
|
|
|
|
|
else if (~c)
|
|
|
|
|
|
printf("column %lld\n", c);
|
|
|
|
|
|
else
|
|
|
|
|
|
printf("impossible\n");
|
|
|
|
|
|
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
