← 返回题目列表

AtCoder · arc169_d

D. 添加进行排列

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

分数: 700 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N。 的每个元素 A 是介于 0 和 N-1,包括在内。

您可以执行以下操作零次或多次:

  • 准确选择 M 元素来自 A。 然后,将每个选定元素的值增加 1。 现在,如果某些元素的值为 N,将这些值更改为 0.

你的目标是 A 的排列 (0,1,\cdots,N-1)。 确定目标是否可以实现。如果是,求所需的最少操作次数。

约束

  • 2 \leq N \leq 250000
  • 1 \leq M \leq N-1
  • 0 \leq A_i \leq N-1
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \cdots A_N

输出

如果目标无法实现,则打印 -1。 否则,打印所需的最少操作数。


示例输入 1

3 2
0 1 1

示例输出 1

2

您可以通过如下操作,分两次操作来达到目的:

  • 初始状态: A=(0,1,1).
  • 第一个操作:选择 A_1 和 A_2, 制作 A=(1,2,1).
  • 第二次操作:选择 A_2 和 A_3, 制作 A=(1,0,2).

您无法通过少于两次操作来实现目标,因此答案是 2.


示例输入 2

5 2
0 4 2 3 1

示例输出 2

0

示例输入 3

4 2
0 0 1 2

示例输出 3

-1

示例输入 4

20 15
5 14 18 0 8 5 0 10 6 5 11 2 10 10 17 9 8 14 4 4

示例输出 4

10