#3175. 「IOI2019」排列鞋子

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

Adnan 拥有巴库最大的鞋店。现在有一个装着 n 双鞋的箱子刚运到他的鞋店。每双鞋是大小相同的两只:一只左脚,一只右脚。Adnan 把这 2n 只鞋排成一行,该行总共有 2n 位置,从左到右编号为 0 2n-1

Adnan 想把这些鞋子重新排成合法的排列。一个排列是合法的,当且仅当对于所有的 i\ (0\le i\le n-1) ,以下条件都成立:

  • 在位置 2i 2i+1 上的鞋子大小相同;
  • 在位置 2i 上的鞋子是一只左脚鞋;
  • 在位置 2i+1 上的鞋子是一只右脚鞋。

为实现上述目标,Adnan 可以做一系列对调。在每次对调中,他选择当前相邻的两只鞋进行对调(也就是把它们拿起来,然后将每只鞋子放回到另一只鞋子原来的位置上)。两只鞋子是相邻的,如果其位置编号的差为 1

请求出 Adnan 最少要做出多少次对调,才能得到一个合法排列。

输入格式

第一行一个正整数 n ,表示有 n 双鞋。

第二行 2n 个整数 S_i ,第 i 个整数表示位置编号为 i-1 的鞋子。其中 |S_i|\neq 0 ,等于最初在位置 i 上的鞋子的大小。这里 |x| 表示 x 的绝对值,当 x>0 时等于 x ,当 x<0 时等于 -x 。如果 S_i<0 ,则 i 位置上的鞋子是一只左脚鞋,否则是右脚鞋。

输出格式

输出一行一个整数,表示最少对调次数。

样例

样例输入 1

2
2 1 -1 -2

样例输出 1

4

样例说明 1

Adnan 可以通过 4 次对调而得到一个合法的排列。

例如,他可以先对调 1 -1 ,再对调 1 -2 ,再对调 -1 -2 。最后对调 -2 2 。随后他就可以得到合法的排列 [-2,2,-1,1] 。无法用少于 4 次对调就得到合法的排列,因此输出 4

shoes.png

样例输入 2

3
-2 2 2 -2 -2 2

样例输出 2

1

样例说明 2

Adnan 可以对调在位置 2 3 上的鞋子来得到合法的排列 [-2, 2, -2, 2, -2, 2] ,因此应当输出 1

数据范围与提示

对于所有数据:

  • 1\le n\le 10^5
  • 对于所有 i\ (0\le i\le 2n-1) ,都有 1\le |S_{i+1}|\le n
  • 总有某个合法的排列可以经由一系列对调而得到。

详细子任务附加限制与分值如下表:

子任务编号 附加限制 分值
1 n=1 10
2 n\le 8 20
3 所有鞋子大小都是相同的
4 所有在位置 0,\ldots,n-1 上的鞋都是左脚鞋,而在位置 n,\ldots,2n-1 上的鞋都是右脚鞋。而且对于所有 i\ (0\le i\le n-1) ,在位置 i i+n 上的鞋子大小相同 15
5 n\le 10^3 20
6 无附加限制 15