← 返回题目列表

AtCoder · awc0064_e

E. 通过相邻交换减少反转

中文机器翻译题面 查看原题

分数: 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