XX Open Cup Grand Prix of Korea H.Maximizer @ Wings            分类 ACM
发布于 星期六, 十二月 12 日, 2020 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

给出长度为$n$的两个全排列$a, b$, 一次操作能交换$a$中两个相邻的元素, 求最小交换次数, 使得$\sum_{i=1}^n \mid a_i - b_i \mid$最大.

题解

先来考虑$n$为偶数的情况. 要使得$\sum_{i=1}^n \mid a_i - b_i \mid$最大, 可以发现, $a, b$对应的元素$a_i, b_i$, 应该满足$a_i \le \frac{n}{2}, b_i > \frac{n}{2}$, 或者$a_i > \frac{n}{2}, b_i \le \frac{n}{2}$. 证明显然, 略(懒).

所以可以转化成$01$序列: $x \le \frac{n}{2}$的为$0$, 否则为$1$. 然后将$b$取反, 就得到了$a$的目标$a'$. “交换相邻元素"等价于求逆序对, 这个转化方法适用于所有序列, 包括有可重元素的数列, 当然包括$01$序列.

但是这里的$a'$不是按顺序排的, 所以直接求$a$的逆序对是不可行的.

下面有两种解决方法, 第一是构造一个最优的排列, 求逆序对.

将$a'$的下标数组$p_{a'}$取出, 按照贪心, 对$a$求一个排列$p$. 如:

$$ \begin{aligned} a = &\{1, 1, 0, 1, 0, 0\} \newline a' = &\{0, 1, 0, 0, 1, 1\} \end{aligned} $$

$a'$的下标取出

$$ \begin{aligned} a' = &\{0, 1, 0, 0, 1, 1\} \newline p_{a'} = &\{1, 2, 3, 4, 5, 6\} \end{aligned} $$

那么:

  • $a$的第一个数是$1$, 找到$a'$中第一个$1$的下标, 为$2$, 所以$p$的第一个元素为$2$;
  • $a$的第二个数是$1$, 找到$a'$中第二个$1$的下标, 为$5$, 所以$p$的第二个元素为$5$;
  • $a$的第二个数是$0$, 找到$a'$中第一个$0$的下标, 为$1$, 所以$p$的第二个元素为$1$

$\dots$

这样就得到了一个全排列$p$, 对$p$求逆序对, 即是交换次数.

奇数暂不讨论, 往下看有.

复杂度$O(nlogn)$

第二种方法:

只有$0$和$1$, 根据上述贪心方法, 可以发现, 其实我们是把$a$中第$i$个$1$和$a'$中第$i$个$1$“配对”. $0$同理.

简单证明一下:

不失一般性, 以$1$的配对为例. 如果不是这样, 那么在交换的过程中某一个$1$会"跨过"另一个$1$去配对, 被"跨过"的$1$位置已经改变, 如果改变以后朝着他的配对位置移动, 则答案不变; 如果朝着配对位置相反的方向移动, 则需要多移动一次, 不如直接让这个被跨过的$1$去配对当前$1$的配对位置.

证毕.

由于只有$01$序列, 我们只要把$1$配对了, $0$一定也是配对的. 并且这样的配对方式不会影响到其他$1$的移动次数, 所以我们只需要对每个一$1$, 计算他在两个数组中下标的差即可.

$n$是奇数的情况就很好考虑了. $\lceil \frac{n}{2} \rceil$既可以与小的配对, 也可以与大的配对, 因为和谁配对都不会改变答案. 所以我们让他分别是$1, 0$做两遍, 去最小答案即可.

复杂度$O(n)$

代码

(没写$O(nlogn)$的傻子做法)

const int maxn = 2.5e5 + 10;

int n, a[maxn], b[maxn];
LL ans;
vector<int> sa, sb;

LL sol() {
	LL res = 0;
	sa.clear();
	sb.clear();
	for (int i = 1; i <= n; i++) {
		if (a[i])
			sa.push_back(i);
		if (b[i])
			sb.push_back(i);
	}
	for (int i = 0; i < sa.size(); i++)
		res += llabs(sa[i] - sb[i]);
	return res;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for (int i = 1; i <= n; i++)
		scanf("%d", b + i);
	if ((n&1) == 0) {
		for (int i = 1; i <= n; i++) {
			a[i] = (a[i] > n/2);
			b[i] = (b[i] <= n/2);
		}
		ans = sol();
	}
	else {
		int pa = -1, pb = -1;
		for (int i = 1; i <= n; i++) {
			if (a[i] == n/2 + 1)
				pa = i;
			if (b[i] == n/2 + 1)
				pb = i;
			a[i] = a[i] > n/2 + 1;
			b[i] = b[i] <= n/2;
		}
		a[pa] = 1, b[pb] = 1;
		ans = sol();
		a[pa] = 0, b[pb] = 0;
		ans = min(ans, sol());
	}
	printf("%lld\n", ans);
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch