外国大气网站设计,网站建设与管理期末总结,网站推广计划效果,空中客车网站建设需求题目
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是 TYVJ 今年举办了一次线下七夕祭。
Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕#xff0c;于是他们决定去 TYVJ 七夕祭游玩。
TYVJ 七夕祭和 11 区的夏祭的形式很像。
矩形的祭典会场由 N N N 排 …题目
七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。
于是 TYVJ 今年举办了一次线下七夕祭。
Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕于是他们决定去 TYVJ 七夕祭游玩。
TYVJ 七夕祭和 11 区的夏祭的形式很像。
矩形的祭典会场由 N N N 排 M M M 列共计 N × M N×M N×M 个摊点组成。
虽然摊点种类繁多不过 cl 只对其中的一部分摊点感兴趣比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。
Vani 预先联系了七夕祭的负责人 zhq希望能够通过恰当地布置会场使得各行中 cl 感兴趣的摊点数一样多并且各列中 cl 感兴趣的摊点数也一样多。
不过 zhq 告诉 Vani摊点已经随意布置完毕了如果想满足 cl 的要求唯一的调整方式就是交换两个相邻的摊点。
两个摊点相邻当且仅当他们处在同一行或者同一列的相邻位置上。
由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间每一行或每一列的第一个位置和最后一个位置也算作相邻。
现在 Vani 想知道他的两个要求最多能满足多少个。
在此前提下至少需要交换多少次摊点。
输入格式
第一行包含三个整数 N N N 和 M M M 和 T T T T T T 表示 cl 对多少个摊点感兴趣。
接下来 T 行每行两个整数 x , y x,y x,y表示 cl 对处在第 x x x 行第 y y y 列的摊点感兴趣。
输出格式
首先输出一个字符串。
如果能满足 Vani 的全部两个要求输出 both
如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多输出 row
如果只能使各列中 cl 感兴趣的摊点数一样多输出 column
如果均不能满足输出 impossible。
如果输出的字符串不是 impossible 接下来输出最小交换次数与字符串之间用一个空格隔开。
数据范围 1 ≤ N , M ≤ 100000 1≤N,M≤100000 1≤N,M≤100000 0 ≤ T ≤ min ( N ∗ M , 100000 ) 0≤T≤\min(N∗M,100000) 0≤T≤min(N∗M,100000) 1 ≤ x ≤ N 1≤x≤N 1≤x≤N 1 ≤ y ≤ M 1≤y≤M 1≤y≤M
输入样例
2 3 4
1 3
2 1
2 2
2 3输出样例
row 1分析 整体思路 经过分析可以发现交换左右两个相邻的摊点只会改变某两列中 cl 感兴趣的摊点数不会改变每行中 cl 感兴趣的摊点数。同理交换上下两个相邻的摊点只会改变某两行中 cl 感兴趣的摊点数不会改变每列中 cl 感兴趣的摊点数。所有可以把本题分成两个互相独立的部分计算。
通过最少次数的左右交换使每列中 cl 感兴趣的摊点数相同。通过最少次数的上下交换使每行中 cl 感兴趣的摊点数相同。
以第 1 个问题为例进行探讨。
可以统计出在初始情况下每列中 cl 感兴趣的摊点总数记为 C [ 1 ] C[1] C[1] ~ C [ M ] C[M] C[M]。若 cl 感兴趣的摊点总数 T T T 不能被 M M M 整除则不可能达到要求。若 T T T 能被 M M M 整除则目标就是让每列中有 T / M T/M T/M 个 cl 感兴趣的摊点。
思考到这里可能已经想到了一个与此类似的经典问题 “均分纸牌”。 「均分纸牌」问题 “均分纸牌”问题是说有 M M M 个人排成一行他们手中分别有 C [ 1 ] C[1] C[1] ~ C [ M ] C[M] C[M] 张纸牌在每一步操作中可以让某个人把自己手中的一张纸牌交给他旁边的一个人求至少需要多少步操作才能让每个人手中持有的纸牌数相等。显然当所有人手中持有的纸牌总数 T T T 能被 M M M 整除时“均分纸牌” 问题有解在有解时可以先考虑第一个人。
若 C [ 1 ] T / M C[1] T/M C[1]T/M则第一个人需要给第二个人 C [ 1 ] − T / M C[1] - T/M C[1]−T/M 张纸牌即把 C [ 2 ] C[2] C[2] 加上 C [ 1 ] − T / M C[1] - T/M C[1]−T/M。若 C [ 1 ] T / M C[1] T/M C[1]T/M则第一个人需要从第二个人手中拿 T / M − C [ 1 ] T/M - C[1] T/M−C[1] 张纸牌即把 C [ 2 ] C[2] C[2] 减去 T / M − C [ 1 ] T/M - C[1] T/M−C[1]。
按照同样的方法依次考虑第 2 ~ M M M 个人。即使在某个时刻有某个 C [ i ] C[i] C[i] 被减为负数也没有关系因为接下来 C [ i ] C[i] C[i] 就会从 C [ i 1 ] C[i1] C[i1] 处拿牌在实际中可以认为 C [ i ] C[i] C[i] 从 C [ i 1 ] C[i1] C[i1] 处拿牌发生在 C [ i − 1 ] C[i-1] C[i−1] 从 C [ i ] C[i] C[i] 处拿牌之前。按照这种方法经过计算达到目标所需要的最少步数其实就是 ∑ i 1 M ∣ i ∗ T M − G [ i ] ∣ 其中 G 是 C 的前缀和即 G [ i ] ∑ j 1 i C [ j ] \sum_{i1}^M|i * \frac{T}{M} - G[i]|其中 G 是 C 的前缀和即 G[i] \sum_{j 1}^{i}C[j] i1∑M∣i∗MT−G[i]∣其中G是C的前缀和即G[i]j1∑iC[j] 其含义是每个 “前缀” 最初共持有 G [ i ] G[i] G[i] 张纸牌最终会持有 i ∗ T / M i * T/M i∗T/M 张纸牌多退少补会与后边的人发生 “二者之差的绝对值” 张纸牌的交换。
如果设 A [ i ] C [ i ] − T / M A[i] C[i] - T/M A[i]C[i]−T/M即一开始就让每个人手中的纸牌数都减掉 T / M T/M T/M并且最终让每个人手里都恰好 0 张牌答案显然不变就是 ∑ i 1 M ∣ S [ i ] ∣ 其中 S 是 A 的前缀和即 S [ i ] ∑ j 1 i A [ j ] \sum_{i1}^M|S[i]|其中 S 是 A 的前缀和即 S[i] \sum_{j 1}^i A[j] i1∑M∣S[i]∣其中S是A的前缀和即S[i]j1∑iA[j]
从数学的角度以上两个公式也可以互相推导得到。 「环形均分纸牌」问题 回到本题如果不考虑 “第 1 列与最后一列也是相邻的” 这一条件那么刚才提到的本题中的第 1 个问题与 “均分纸牌” 问题是等价的。若问题有解一定存在一种适当的顺序使得每一步传递纸牌的操作可以转化为交换一对左右相邻的摊点其中 cl 恰好对这两个摊点之一感兴趣。
若第 1 列与最后一列相邻则问题等价于一个 “环形均分纸牌”。仔细思考可以发现一定存在一种最优解的方案环上某两个相邻的人之间没有发生纸牌交换操作。于是有一种朴素的做法是枚举这个没有发生交换的位置把环断开看成一行转化为一般的 “均分纸牌” 问题进行计算。
首先一般的 “均分纸牌” 问题就相当于在第 M M M 个人与第 1 个人之间把环断开此时这 M M M 个人写成一行其持有的牌数、前缀和分别是 A [ 1 ] S [ 1 ] A [ 2 ] S [ 2 ] . . . . . . A [ M ] S [ M ] A[1] \ \ S[1] \\ A[2] \ \ S[2] \\ ... \ \ ... \\ A[M] \ \ S[M] A[1] S[1]A[2] S[2]... ...A[M] S[M] 如果在第 k k k 个人之后把环断开写成一行这 M M M 个人持有的纸牌数、前缀和分别是 A [ k 1 ] S [ k 1 ] − S [ k ] A [ k 2 ] S [ k 2 ] − S [ k ] . . . . . . A [ M ] S [ M ] − S [ k ] A [ 1 ] S [ 1 ] S [ M ] − S [ k ] . . . . . . A [ k ] S [ k ] S [ M ] − S [ k ] A[k 1] \space\space\space\space\space S[k1] - S[k] \\ A[k2] \space\space\space\space\space S[k2]-S[k] \\ ... \space\space\space\space\space... \\ A[M] \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space S[M] -S[k] \\ A[1] \space\space\space\space\space\space\space\space S[1] S[M] - S[k] \\ ... \space\space\space\space\space ... \\ A[k] \space\space\space\space\space S[k] S[M] - S[k] A[k1] S[k1]−S[k]A[k2] S[k2]−S[k]... ...A[M] S[M]−S[k]A[1] S[1]S[M]−S[k]... ...A[k] S[k]S[M]−S[k] 注意此处 A A A 是减去最终每个人手里纸牌数 T / M T/M T/M 之后的数组 A A A 数组均分之后每个人手里都有 0 张纸牌所以 S [ M ] 0 S[M] 0 S[M]0。也就是说从第 k k k 个人把环断开写成一行前缀和数组的变化是每个位置都减去 S [ k ] S[k] S[k]。
根据上面推导的公式所需最小步数为 ∑ i 1 M ∣ S [ i ] − S [ k ] ∣ 其中 S 是 A 的前缀和即 S [ i ] ∑ j 1 i A [ j ] \sum_{i 1}^M |S[i] - S[k]|其中 S 是 A 的前缀和即 S[i] \sum_{j 1}^iA[j] i1∑M∣S[i]−S[k]∣其中S是A的前缀和即S[i]j1∑iA[j]
当 k k k 取何值时上式最小这就是 “AcWing104.货仓选址” 问题其中 S [ i ] S[i] S[i] 是数轴上 M M M 家商店的位置 S [ k ] S[k] S[k] 是货仓的位置 ∣ S [ i ] − S [ k ] ∣ |S[i] - S[k]| ∣S[i]−S[k]∣ 就是二者之间的距离。根本不需要枚举 k k k只需要把 S S S 从小到大排序取中位数作为 S [ k ] S[k] S[k] 就是最优解至此本题得到完美解决时间复杂度为 O ( N l o g N M l o g N ) O(N logN MlogN) O(NlogNMlogN)。 思路总结 综上所述本题可类比为行、列方向上的两次 “环形均分纸牌” 问题。环形均分纸牌又类比为 “均分纸牌” 与 “货仓选址” 问题。其中的每一步都仅使用了基本算法和性质最后转化为了简单而经典的问题。
代码
#include iostream
#include algorithm
using namespace std;#define ll long long
const int N 1e5 10;int n, m, t, a[N], b[N]; //a数组记录每行感兴趣的摊点个数b数组记录每列感兴趣的摊点个数
ll s[N]; //前缀和数组int func(int *arr, int x) {ll sum 0;int avg t / x; //每行/列应该多少个摊点for (int i 1; i x; i) arr[i] - avg; //每行/列减去平均的摊点个数s[0] 0;for (int i 1; i x; i) s[i] s[i - 1] arr[i];//求前缀和sort(s 1, s 1 x); //排序for (int i 1; i x; i) sum abs(s[i] - s[(x 1) / 2]); //s[(x 1) / 2]为中位数return sum;
}int main() {cin n m t;int x, y;for (int i 1; i t; i) {cin x y;a[x];b[y];}bool row !(t % n), col !(t % m);if (row col) {cout both ;} else if(row) {cout row ;} else if (col) {cout column ;} else {cout impossible endl;return 0;}ll ans 0;if (row) {ans func(a, n);} if (col) {ans func(b, m);}cout ans endl;return 0;
}
