← 返回题目列表

AtCoder · codefestival_2016_qualC_b

B. K蛋糕

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

分数: 200 点

问题陈述

有 K 蛋糕片。 高桥先生想每天吃一个蛋糕, K 天把它们全部吃掉。

有 T 蛋糕种类,以及该类型蛋糕的数量 i (1 ≤ i ≤ T) 是 a_i.

连续两天吃同一种蛋糕就没意思了, 因此,高桥先生想决定吃蛋糕的顺序,以尽量减少他必须吃与前一天相同类型的蛋糕的天数。

计算吃与前一天相同类型的蛋糕的最少天数。

约束

  • 1 ≤ K ≤ 10000
  • 1 ≤ T ≤ 100
  • 1 ≤ a_i ≤ 100
  • a_1 + a_2 + ... + a_T = K

输入

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

K T
a_1 a_2 ... a_T

输出

打印出吃与前一天相同类型的蛋糕的最少天数。


示例输入 1

7 3
3 2 2

示例输出 1

0

例如,如果高桥先生按照以下顺序吃蛋糕 2, 1, 2, 3, 1, 3, 1,他可以避免吃与前一天相同类型的蛋糕。


示例输入 2

6 3
1 4 1

示例输出 2

1

有 6 蛋糕。 例如,如果高桥先生吃蛋糕的顺序是 2, 3, 2, 2, 1, 2,他必须吃相同类型的蛋糕(即类型 2)仅在第四天作为前一天。 由于这是最小数,所以答案是 1.


示例输入 3

100 1
100

示例输出 3

99

由于高桥先生只有一种蛋糕,所以从第二天起他只能吃与前一天相同类型的蛋糕。