分数: 400 点
问题陈述
我们有一个长度为的整数序列 N: A=(A_1,A_2,\cdots,A_N)。 下面在这个问题中,让 分数 of A 是第一个的总和 K 条款 A。 另外,让 s 是序列的分数 A 在输入中给出。
您可以多次执行以下操作。
- 选择两个相邻元素 A 并交换它们。
你的目标是至少获得分数 s+1。 确定目标是否可以实现。如果是,找出实现它所需的最少操作数。
约束
- 2 \leq N \leq 4 \times 10^5
- 1 \leq K \leq N-1
- 1 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \cdots A_N
输出
如果目标无法实现,请打印 -1。
如果可以实现,请打印实现它所需的最少操作数。
示例输入 1
4 2 2 1 1 2
示例输出 1
2
我们有 s=2+1=3。 以下操作顺序使分数至少 4.
- (2,1,1,2) \to (交换 A_3 和 A_4)\to (2,1,2,1) \to (交换 A_2 和 A_3)\to (2,2,1,1)
一次操作无法实现该目标,因此所需的最少操作次数为 2.
示例输入 2
3 1 3 2 1
示例输出 2
-1
示例输入 3
20 13 90699850 344821203 373822335 437633059 534203117 523743511 568996900 694866636 683864672 836230375 751240939 942020833 865334948 142779837 22252499 197049878 303376519 366683358 545670804 580980054
示例输出 3
13