分数: 466 分
问题陈述
高桥有 N 卡片水平排列。每张卡都有一个编号 上面写着 1 to N ,目前是按顺序排列的 P_1, P_2, \ldots, P_N 从左到右。
高桥的目标是按数字升序排列卡片(即, 1, 2, \ldots, N 从左到右)。为了衡量排列的无序程度,他使用 反转计数.
卡序列的反转计数 Q_1, Q_2, \ldots, Q_N 是对数 (i, j) 满意 1 \leq i < j \leq N 这样 Q_i > Q_j.
Takahashi 可以执行选择两张相邻卡牌并交换其位置的操作。他最多可以执行这个操作 K 次,并且在每次操作中,他可以自由选择任何相邻的对进行交换(同一对可以被选择多次)。
当高桥以最佳方式执行运算以最小化反转计数时,找到运算后可以实现的卡序列的最小反转计数。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^{18}
- (P_1, P_2, \ldots, P_N) 是一个排列 (1, 2, \ldots, N)
- 所有输入均为整数
输入
N K P_1 P_2 \ldots P_N
- 第一行包含一个整数 N 代表卡片数量和一个整数 K 代表最大操作次数,以空格分隔。
- 第二行包含整数 P_1, P_2, \ldots, P_N 代表当前卡片的顺序,以空格分隔。这是一个排列 1 通过 N.
输出
一行打印高桥最多执行完后能够达到的卡片序列的最小反转次数 K 相邻交换操作。
示例输入 1
5 2 3 1 4 5 2
示例输出 1
2
示例输入 2
3 100 3 2 1
示例输出 2
0
示例输入 3
10 5 5 3 8 1 7 2 10 4 6 9
示例输出 3
12