#P15619. [2023年保加利亚国家队组队赛Junior]Swaps交换

    ID: 14831 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>算法基础贪心排序数据结构树状数组CF2200

[2023年保加利亚国家队组队赛Junior]Swaps交换

题目描述

Sashka 有一个排列,而且不是普通排列,而是一个长度为 2N2N 的排列:

p1,p2,…,p2N,p_1,p_2,\ldots,p_{2N},

它由 11 到 2N2N 的所有整数各出现一次组成。

她想把这个排列按升序排序。为此,她可以使用两类交换操作。

操作 1

选择两个整数 x,yx,y,满足 1≤x,y≤N1\le x,y\le N,然后同时交换:

p2x−1↔p2y−1,p_{2x-1} \leftrightarrow p_{2y-1},

以及

p2x↔p2y.p_{2x} \leftrightarrow p_{2y}.

也就是说,可以把第 xx 个长度为 22 的块和第 yy 个长度为 22 的块整体交换。

该操作费用为 00 元。

操作 2

选择一个整数 xx,满足 1≤x<2N1\le x<2N,然后交换相邻两个元素:

px↔px+1.p_x \leftrightarrow p_{x+1}.

该操作费用为 11 元。

Sashka 有一个限制:一旦她使用过操作 2,就不能再使用操作 1。也就是说,她必须先进行若干次操作 1,然后再进行若干次操作 2。

她想知道,为了把排列排成升序,最少需要花费多少元。

请你编写程序求出这个最小费用。

输入格式

第一行输入一个正整数 NN。

第二行输入 2N2N 个整数:

p1,p2,…,p2N.p_1,p_2,\ldots,p_{2N}.

输出格式

输出一个整数,表示最小可能费用。

数据范围

  • 1≤N≤1051 \le N \le 10^5
  • 1≤pi≤2N1 \le p_i \le 2N
  • 对任意 i≠ji\ne j,有 pi≠pjp_i\ne p_j

子任务

子任务 NN 其他限制 依赖子任务 分值
1 - 样例 - 0
2 ≤3\le 3 - 9
3 ≤8\le 8 1-2
4 ≤16\le 16 1-3 10
5 ≤50\le 50 1-4
6 ≤150\le 150 1-5 9
7 ≤250\le 250 1-6 7
8 ≤1000\le 1000 1-7 11
9 ≤3000\le 3000 1-8 10
10 ≤100000\le 100000 1-9 25

只有当某个子任务及其所依赖的子任务全部通过时,才能获得该子任务的分数。

样例 1

输入

1
2 1

输出

1

样例 2

输入

3
6 5 1 4 3 2

输出

4

难度评估

操作 1 只能交换长度为 22 的块,不能改变每个块内部两个元素的相对顺序;操作 2 的最小费用等于最终排列中的逆序数。因此题目可以理解为:任意重排这些长度为 22 的块,使重排后的总逆序数最小。

题解中的关键结论是:先把每个块内部较小的数放前面,若原来块内逆序则答案先加 11;随后把这些二元组按某个合法关键字排序,例如按 max(a,b) 或按 a+b 排序,都可以得到最优块顺序。最后对拼接后的长度 2N2N 序列计算逆序数即可。

实现本身并不长:排序二元组,然后用归并排序或树状数组统计逆序数。但正确性证明不直观,尤其是为什么这样排序二元组一定最优。

建议 CF 评分:2200。