【算法】七夕祭
题目
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是 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题目来自：105. 七夕祭 - AcWing题库