Building a Tall Barn

题目描述

Farmer John 正在建造一座全新的、共有 $N$ 层的谷仓，并在他的 $K$ 头奶牛的帮助下完成（$1 \leq N \leq K \leq 10^{12}$ 且 $N \leq 10^5$）。为了尽可能快地完成建造，他需要你帮助计算如何在奶牛之间分配工作。 每头奶牛必须被分配去负责谷仓总共 $N$ 层中的恰好一层，并且每一层都必须至少分配到一头奶牛。第 $i$ 层需要总计 $a_i$ 单位的工作量，每头奶牛每小时完成 1 单位工作量，因此如果有 $c$ 头奶牛在第 $i$ 层工作，则该层将在 $a_i / c$ 的时间内完成。出于安全原因，必须先完成第 $i$ 层，才能开始建造第 $i+1$ 层。 请计算在以最优方式分配奶牛到各层工作的情况下，完成整个谷仓所需的最小总时间。请将该数四舍五入到最接近的整数；保证答案距离任意两个相邻整数的分界点至少有 0.1。

输入格式

第一行输入包含 $N$ 和 $K$。 接下来 $N$ 行包含 $a_1 \ldots a_N$，每个都是正整数，大小不超过 $10^{12}$。

输出格式

请输出建造谷仓所需的最少时间，并将其四舍五入到最接近的整数。

2 5
10
4

5

提示

题目来源：Yang Liu

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum