AT_abc480_f.Cake Cutting

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN cakes, and the size of the ii-th cake is AiA_i. You are going to distribute these cakes to MM people.

Let SS be the total size of the cakes, A1+⋯+ANA_1+\dots+A_N. Here, it is guaranteed that SS is a multiple of MM.

You can perform the following operation any number of times (possibly zero) in any order.

  • Choose one cake and cut it into 22 pieces in any way you like (the sizes need not be integers).

After the operations, you distribute the cakes to the MM people. Find the minimum number of operations required so that the total size of the cakes each person receives is SM\frac{S}{M}.

A more formal statement is as follows.

  • You are given a sequence A=(A1,…,AN)A=(A_1,\dots,A_N) and a positive integer MM. Let S=∑iAiS=\sum_i A_i.
  • You can perform the following operation any number of times.
    • Choose an integer ii with 1≤i≤∣A∣1\leq i \leq |A| and a real number xx with 0<x<Ai0 < x < A_i. Replace AA with the sequence of length ∣A∣+1|A|+1 obtained by appending x,Ai−xx,A_i-x to the end of AA and removing the ii-th element.
  • Find the minimum number of operations required for there to exist a P\mathcal{P} satisfying all of the following conditions.
    • P\mathcal{P} is a partition of 1,2,…,∣A∣{1,2,\dots,|A|}; that is, it is a set satisfying the following 33 conditions.
      • Each element of P\mathcal{P} is a subset of 1,2,…,∣A∣{1,2,\dots,|A|}.
      • If X,Y∈PX,Y \in \mathcal{P} and X≠YX\neq Y, then X∩Y=∅X \cap Y = \emptyset.
      • ⋃X∈PX=1,2,…,∣A∣\bigcup_{X \in \mathcal{P}}X={1,2,\dots,|A|} holds.
    • ∑i∈XAi=SM\sum_{i\in X}A_i=\frac{S}{M} holds for every X∈PX\in \mathcal{P}.

有 NN 个蛋糕,第 ii 个蛋糕的大小为 AiA_i。你需要将这些蛋糕分给 MM 个人。

令 SS 表示所有蛋糕的总大小,即 A1+⋯+ANA_1+\dots+A_N。题目保证 SS 是 MM 的倍数。

你可以执行以下操作任意多次(包括零次),且顺序任意:

  • 任选一个蛋糕,并将其任意切成两块(切出的两块大小不必为整数)。

操作完成后,你将所有蛋糕分给 MM 个人。求使得每个人收到的蛋糕总大小恰好为 SM\frac{S}{M} 所需的最少操作次数。

更形式化的描述如下:

  • 给定一个序列 A=(A1,…,AN)A=(A_1,\dots,A_N) 和一个正整数 MM。令 S=∑iAiS=\sum_i A_i。
  • 你可以执行以下操作任意多次:
    • 选择一个满足 1≤i≤∣A∣1\leq i \leq |A| 的整数 ii,以及一个满足 0<x<Ai0 < x < A_i 的实数 xx;将序列 AA 替换为一个长度为 ∣A∣+1|A|+1 的新序列,该序列由原序列去掉第 ii 个元素后,在末尾添加 xx 和 Ai−xA_i-x 得到。
  • 求使得存在一个满足以下全部条件的划分 P\mathcal{P} 所需的最少操作次数:
    • P\mathcal{P} 是集合 {1,2,…,∣A∣}\{1,2,\dots,|A|\} 的一个划分;即 P\mathcal{P} 是一个满足以下三个条件的集合:
      • P\mathcal{P} 的每个元素都是 {1,2,…,∣A∣}\{1,2,\dots,|A|\} 的子集;
      • 若 X,Y∈PX,Y \in \mathcal{P} 且 X≠YX\neq Y,则 X∩Y=∅X \cap Y = \emptyset;
      • ⋃X∈PX={1,2,…,∣A∣}\bigcup_{X \in \mathcal{P}}X=\{1,2,\dots,|A|\};
    • 对每个 X∈PX\in \mathcal{P},均有 ∑i∈XAi=SM\sum_{i\in X}A_i=\frac{S}{M}。

输入格式

The input is given from Standard Input in the following format:

NN MM
A1A_1 A2A_2 …\dots ANA_N

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

NN MM
A1A_1 A2A_2 …\dots ANA_N

输出格式

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 22 operations as follows.

  • Cut the cake of size 2323 into pieces of sizes 1010 and 1313. The cake sizes become (7,10,13)(7,10,13).
  • Cut the cake of size 1313 into pieces of sizes 1010 and 33. The cake sizes become (7,10,10,3)(7,10,10,3).
  • Give the cakes of sizes 77 and 33 to one person, a cake of size 1010 to another person, and the remaining cake of size 1010 to the last person.

Sample 2 Explanation:
The minimum is achieved by performing 11 operation as follows.

  • Cut the cake of size 12341234 into pieces of sizes 685685 and 549549. The cake sizes become (123,12,1,685,549)(123,12,1,685,549).
  • Give the 44 cakes of sizes 123,12,1,549123,12,1,549 to one person and the cake of size 685685 to the other.

Constraints

  • 1≤N≤201 \leq N \leq 20
  • 1≤M≤1001 \leq M \leq 100
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • A1+⋯+ANA_1+\dots+A_N is a multiple of MM.
  • All input values are integers.

样例 1 解释:
最小操作次数为 22,具体操作如下:

  • 将大小为 2323 的蛋糕切分为大小分别为 1010 和 1313 的两块。此时蛋糕大小变为 (7,10,13)(7,10,13)。
  • 将大小为 1313 的蛋糕切分为大小分别为 1010 和 33 的两块。此时蛋糕大小变为 (7,10,10,3)(7,10,10,3)。
  • 将大小为 77 和 33 的蛋糕分给第一个人,大小为 1010 的蛋糕分给第二个人,剩余大小为 1010 的蛋糕分给第三个人。

样例 2 解释:
最小操作次数为 11,具体操作如下:

  • 将大小为 12341234 的蛋糕切分为大小分别为 685685 和 549549 的两块。此时蛋糕大小变为 (123,12,1,685,549)(123,12,1,685,549)。
  • 将大小为 123123、1212、11、549549 的四块蛋糕分给第一个人,大小为 685685 的蛋糕分给第二个人。

约束条件

  • 1≤N≤201 \leq N \leq 20
  • 1≤M≤1001 \leq M \leq 100
  • 1≤Ai≤1091 \leq A_i \leq 10^9
  • A1+⋯+ANA_1+\dots+A_N 是 MM 的倍数。
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页