切蛋糕

题目描述

有 $N$ 个蛋糕，第 $i$ 个蛋糕的大小为 $A_i$。你要把这些蛋糕分给 $M$ 个人。

设所有蛋糕的大小之和为 $S=A_1+\dots+A_N$，保证 $S$ 是 $M$ 的倍数。

你可以按任意顺序进行任意多次（包括 $0$ 次）以下操作：

• 选择一个蛋糕，把它任意切成两块（两块的大小不必是整数）。

操作结束后，你把切好的蛋糕分给这 $M$ 个人。请求出：为了让每个人分到的蛋糕大小之和都等于 $\frac{S}{M}$，最少需要进行多少次操作。

形式化地说：

• 给定正整数序列 $A=(A_1,\dots,A_N)$ 和正整数 $M$，令 $S=\sum_i A_i$。
• 你可以进行任意多次以下操作：选择 $1\le i\le |A|$ 和实数 $0<x<A_i$，删去第 $i$ 个数，并在序列末尾加入 $x$ 和 $A_i-x$。
• 请求出最少需要多少次操作，才能存在一个划分 $\mathcal{P}$ 满足：$\mathcal{P}$ 是 $\{1,2,\dots,|A|\}$ 的一个划分，且对每个 $X\in\mathcal{P}$ 都有 $\sum_{i\in X}A_i=\frac{S}{M}$。

输入格式

第一行两个整数 $N, M$。

第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

输出一个整数，表示最少需要的操作次数。

2 3
7 23

2

样例 1 解释

把大小为 $23$ 的蛋糕切成 $10$ 和 $13$，再把大小为 $13$ 的蛋糕切成 $10$ 和 $3$，共操作 $2$ 次。 此时蛋糕为 $7,10,3,10$，可以分成 $\{7,3\}$、$\{10\}$、$\{10\}$ 三组，每组大小都是 $10$，而 $10=\frac{7+23}{3}$。

4 2
1234 123 12 1

1

样例 2 解释

把大小为 $1234$ 的蛋糕切成 $685$ 和 $549$，其余蛋糕不动。 此时可以分成 $\{549,123,12,1\}$ 和 $\{685\}$ 两组，总大小分别为 $685$ 和 $685$。

数据范围

对于所有测试数据，保证：

• $1\le N\le 20$；
• $1\le M\le 100$；
• $1\le A_i\le 10^9$；
• $A_1+\dots+A_N$ 是 $M$ 的倍数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。