AT_abc480_f.Cake Cutting
提高+/省选-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N cakes, and the size of the i-th cake is Ai. You are going to distribute these cakes to M people.
Let S be the total size of the cakes, A1+⋯+AN. Here, it is guaranteed that S is a multiple of M.
You can perform the following operation any number of times (possibly zero) in any order.
- Choose one cake and cut it into 2 pieces in any way you like (the sizes need not be integers).
After the operations, you distribute the cakes to the M people. Find the minimum number of operations required so that the total size of the cakes each person receives is MS.
A more formal statement is as follows.
- You are given a sequence A=(A1,…,AN) and a positive integer M. Let S=∑iAi.
- You can perform the following operation any number of times.
- Choose an integer i with 1≤i≤∣A∣ and a real number x with 0<x<Ai. Replace A with the sequence of length ∣A∣+1 obtained by appending x,Ai−x to the end of A and removing the i-th element.
- Find the minimum number of operations required for there to exist a P satisfying all of the following conditions.
- P is a partition of 1,2,…,∣A∣; that is, it is a set satisfying the following 3 conditions.
- Each element of P is a subset of 1,2,…,∣A∣.
- If X,Y∈P and X=Y, then X∩Y=∅.
- ⋃X∈PX=1,2,…,∣A∣ holds.
- ∑i∈XAi=MS holds for every X∈P.
- P is a partition of 1,2,…,∣A∣; that is, it is a set satisfying the following 3 conditions.
有 N 个蛋糕,第 i 个蛋糕的大小为 Ai。你需要将这些蛋糕分给 M 个人。
令 S 表示所有蛋糕的总大小,即 A1+⋯+AN。题目保证 S 是 M 的倍数。
你可以执行以下操作任意多次(包括零次),且顺序任意:
- 任选一个蛋糕,并将其任意切成两块(切出的两块大小不必为整数)。
操作完成后,你将所有蛋糕分给 M 个人。求使得每个人收到的蛋糕总大小恰好为 MS 所需的最少操作次数。
更形式化的描述如下:
- 给定一个序列 A=(A1,…,AN) 和一个正整数 M。令 S=∑iAi。
- 你可以执行以下操作任意多次:
- 选择一个满足 1≤i≤∣A∣ 的整数 i,以及一个满足 0<x<Ai 的实数 x;将序列 A 替换为一个长度为 ∣A∣+1 的新序列,该序列由原序列去掉第 i 个元素后,在末尾添加 x 和 Ai−x 得到。
- 求使得存在一个满足以下全部条件的划分 P 所需的最少操作次数:
- P 是集合 {1,2,…,∣A∣} 的一个划分;即 P 是一个满足以下三个条件的集合:
- P 的每个元素都是 {1,2,…,∣A∣} 的子集;
- 若 X,Y∈P 且 X=Y,则 X∩Y=∅;
- ⋃X∈PX={1,2,…,∣A∣};
- 对每个 X∈P,均有 ∑i∈XAi=MS。
- P 是集合 {1,2,…,∣A∣} 的一个划分;即 P 是一个满足以下三个条件的集合:
输入格式
The input is given from Standard Input in the following format:
N M
A1 A2 … AN
输入从标准输入中按以下格式给出:
N M
A1 A2 … AN
输出格式
Print the answer.
输出答案。
输入输出样例
输入#1
2 3 7 23
输出#1
2
输入#2
4 2 1234 123 12 1
输出#2
1
说明/提示
Sample 1 Explanation:
The minimum is achieved by performing 2 operations as follows.
- Cut the cake of size 23 into pieces of sizes 10 and 13. The cake sizes become (7,10,13).
- Cut the cake of size 13 into pieces of sizes 10 and 3. The cake sizes become (7,10,10,3).
- Give the cakes of sizes 7 and 3 to one person, a cake of size 10 to another person, and the remaining cake of size 10 to the last person.
Sample 2 Explanation:
The minimum is achieved by performing 1 operation as follows.
- Cut the cake of size 1234 into pieces of sizes 685 and 549. The cake sizes become (123,12,1,685,549).
- Give the 4 cakes of sizes 123,12,1,549 to one person and the cake of size 685 to the other.
Constraints
- 1≤N≤20
- 1≤M≤100
- 1≤Ai≤109
- A1+⋯+AN is a multiple of M.
- All input values are integers.
样例 1 解释:
最小操作次数为 2,具体操作如下:
- 将大小为 23 的蛋糕切分为大小分别为 10 和 13 的两块。此时蛋糕大小变为 (7,10,13)。
- 将大小为 13 的蛋糕切分为大小分别为 10 和 3 的两块。此时蛋糕大小变为 (7,10,10,3)。
- 将大小为 7 和 3 的蛋糕分给第一个人,大小为 10 的蛋糕分给第二个人,剩余大小为 10 的蛋糕分给第三个人。
样例 2 解释:
最小操作次数为 1,具体操作如下:
- 将大小为 1234 的蛋糕切分为大小分别为 685 和 549 的两块。此时蛋糕大小变为 (123,12,1,685,549)。
- 将大小为 123、12、1、549 的四块蛋糕分给第一个人,大小为 685 的蛋糕分给第二个人。
约束条件
- 1≤N≤20
- 1≤M≤100
- 1≤Ai≤109
- A1+⋯+AN 是 M 的倍数。
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?