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