[IOI2019] 排列鞋子
题目描述
**由于洛谷数据点限制,本题仅评测其中的 $100$ 个数据点。**
如果需要测试全部数据,有以下两道题:
1. [Subtask 1-3](/problem/U98795)
2. [Subtask 4-6](/problem/U98796)
两题满分均为 $50$ 分,包含 Subtask中所有的测试点。
---
Adnan 拥有巴库最大的鞋店。现在有一个装着 $n$ 双鞋的箱子刚运到他的鞋店。每双鞋是大小相同的两只:一只左脚,一只右脚。Adnan 把这 $2n$ 只鞋排成一行,该行总共有 $2n$ 个**位置**,从左到右编号为 $0$ 到 $2n-1$ 。
Adnan 想把这些鞋子重新排成**合法的排列**。一个排列是合法的,当且仅当对于所有的 $i(0\leqslant i \leqslant n - 1)$,以下条件都成立:
- 在位置 $2i$ 和 $2i+1$ 上的鞋子大小相同;
- 在位置 $2i$ 上的鞋子是一只左脚鞋;
- 在位置 $2i+1$ 上的鞋子是一只右脚鞋。
为实现上述目标,Adnan 可以做一系列对调。在每次对调中,他选择当前**相邻**的两只鞋进行对调(也就是把它们拿起来,然后将每只鞋子放回到另一只鞋子原来的位置上)。两只鞋子是相邻的,当且仅当其位置编号的差为 $1$。
请求出 Adnan 最少要做出多少次对调,才能得到一个合法排列。
输入输出格式
输入格式
第一行一个正整数 $n$,表示有 $n$ 双鞋。
第二行 $2n$ 个整数 $S_i$,第 $i$ 个整数表示位置编号为 $i-1$ 的鞋子。其中 $|S_u|\neq 0$,等于最初在位置 $i$ 上的鞋子的大小。这里 $|x|$ 表示 $x$ 的绝对值,当 $x\geq 0$ 时等于 $x$,当 $x < 0$ 时等于 $-x$。如果 $S_i < 0$,则 $i$ 位置上的鞋子是一只左脚鞋,否则是右脚鞋。
输出格式
输出一行一个整数,表示最少对调次数。
输入输出样例
输入样例 #1
2
2 1 -1 -2
输出样例 #1
4
输入样例 #2
3
-2 2 2 -2 -2 2
输出样例 #2
1
说明
**样例说明 1**
Adnan 可以通过 $4$ 次对调而得到一个合法的排列。
例如,他可以先对调 $1$ 和 $-1$,再对调 $1$ 和 $-2$,再对调 $-1$ 和 $-2$。最后对调 $-2$ 和 $2$。随后他就可以得到合法的排列 。无法用少于 $4$ 次对调就得到合法的排列,因此输出 $4$。
![](https://cdn.luogu.com.cn/upload/image_hosting/ybs09z2e.png)
**样例说明 2**
Adnan 可以对调在位置 $2$ 和 $3$ 上的鞋子来得到合法的排列$[-2,2,-2,2,-2,2]$,因此应当输出 $1$。
**数据范围**
对于所有数据:
- $1\leqslant n\leqslant10^5$;
- 对于所有$i(0\leqslant i\leqslant 2n-1)$,都有$1\leqslant \left|S_{i+1}\right|\leqslant n$;
- 总有某个合法的排列可以经由一系列对调而得到。
详细子任务附加限制与分值如下表:
| 子任务编号 | 附加限制 | 分值 |
|:---:|:---:|:---:|
| $1$ | $n=1$ | $10$|
|$2$|$n\leqslant8$|$20$|
|$3$|所有鞋子大小都是相同的|$20$|
|$4$|所有在位置 $0,\dots,n-1$ 上的鞋都是左脚鞋,而在位置 $n,\dots,2n-1$ 上的鞋都是右脚鞋。而且对于所有 $i(0\leqslant i\leqslant n-1)$,在位置 $i$ 和 $i+n$ 上的鞋子大小相同|$15$|
|$5$|$n\leqslant10^3$|$20$|
|$6$|无附加限制|$15$|