A3092 | 分面包
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
时间限制：1000ms
内存限制：128MB
有一条长度为 $L$ 的面包，现在要将其切割并分给 $N$ 个孩子。
第 $i$ 个孩子 $(1 \leq i \leq N)$ 想要长度为 $A_i$ 的面包。
重复以下操作，将面包切割成长度为 $A_1, A_2, \ldots, A_N$ 的面包分给孩子们。
- 选择一条长度为 $k$ 的面包和一个介于 $1$ 和 $k-1$ 之间（含）的整数 $x$。将面包切割成长度为 $x$ 和 $k-x$ 的两条面包。
- 此操作的花费为 $k$，与 $x$ 的值无关。
每个孩子 $i$ 必须得到一条长度正好为 $A_i$ 的面包，但允许留下未分配的面包。
计算将面包分配给所有孩子所需的最小花费。
$\large{数据范围}$
- $2 \leq N \leq 2\times 10^5$
- $1\leq A_i\leq 10^9$
- $A_1+A_2+\cdots+A_N\leq L\leq 10^{15}$
- 所有输入数值均为整数。
输入格式
对于每个测试文件输入格式如下：
$\tt{A_1\ A_2\ \ldots\ A_N}$
$\tt{N\ L}$
$\tt{A_1\ A_2\ \ldots\ A_N}$
输出格式
输出向所有孩子分发面包所需的最低花费。
输入输出样例
输入 #1
5 7 1 2 1 2 1
输出 #1
16
输入 #2
3 1000000000000000 1000000000 1000000000 1000000000
输出 #2
1000005000000000
样例 $1$：
可以按如下方法为孩子们切面包。
- 选择长度为 $7$ 的面包，令 $x=3$，将其切成长度为 $3$ 和 $4$ 的面包，成本为 $7$ 。
- 选择长度为 $3$ 的面包，令 $x=1$，将其切成长度为 $1$ 和 $2$ 的面包，成本为 $3$ 。把前者给第 $1$ 个孩子。
- 选择长度为 $2$ 的面包，令 $x=1$，将其切成长度为 $1$ 的两个面包，成本为 $2$ 。把它们分给第 $3$ 个和第 $5$ 个孩子。
- 选择长度为 $4$ 的面包，令 $x=2$，将其切成长度为 $2$ 的两个面包，成本为 $4$ 。把它们分给第 $2$ 个和第 $4$ 个孩子。
总共的花费为 $7+3+2+4=16$，无法找到花费更少的切割方案。
样例 $2$：
注意，每个孩子 $i$ 必须收到一个长度正好为 $A_i$ 的面包。
可以按如下方法为孩子们切面包。
- 选择长度为 $7$ 的面包，令 $x=3$，将其切成长度为 $3$ 和 $4$ 的面包，成本为 $7$ 。
- 选择长度为 $3$ 的面包，令 $x=1$，将其切成长度为 $1$ 和 $2$ 的面包，成本为 $3$ 。把前者给第 $1$ 个孩子。
- 选择长度为 $2$ 的面包，令 $x=1$，将其切成长度为 $1$ 的两个面包，成本为 $2$ 。把它们分给第 $3$ 个和第 $5$ 个孩子。
- 选择长度为 $4$ 的面包，令 $x=2$，将其切成长度为 $2$ 的两个面包，成本为 $4$ 。把它们分给第 $2$ 个和第 $4$ 个孩子。
总共的花费为 $7+3+2+4=16$，无法找到花费更少的切割方案。
样例 $2$：
注意，每个孩子 $i$ 必须收到一个长度正好为 $A_i$ 的面包。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？