#P3606. [USACO17JAN] Building a Tall Barn P

[USACO17JAN] Building a Tall Barn P

题目描述

Farmer John is building a brand new, NN-story barn, with the help of his KK cows (1NK10121 \leq N \leq K \leq 10^{12} and N105N \leq 10^5). To build it as quickly as possible, he needs your help to figure out how to allocate work among the cows.

Each cow must be assigned to work on exactly one specific floor out of the NN total floors in the barn, and each floor must have at least one cow assigned to it. The iith floor requires aia_i units of total work, and each cow completes one unit of work per hour, so if cc cows work on floor ii, it will be completed in ai/ca_i / c units of time. For safety reasons, floor ii must be completed before construction can begin on floor i+1i+1.

Please compute the minimum total time in which the barn can be completed, if the cows are allocated to work on floors in an optimal fashion. Output this number rounded to the nearest integer; it is guaranteed that the solution will be more than 0.1 from the boundary between two integers.

FJ正在他的K头奶牛的帮助下建造一个全新的N层谷仓(1<=N<=K<=10^12,N<=10^5)。为了能够尽快的建造它,他需要你帮助他来找出如何在奶牛间分配工作。

每一头牛必须分配到N层中的某一个特定楼层中,并且每一层楼必须至少有一头牛在其中工作。第i层楼需要a[i]个单位的工作,并且每一头牛完成每一单位的工作需要一个单位时间。所以如果有C头牛在第i层工作,那么第i层需要a[i]/c个单位时间。为了安全起见,在施工开始于在第i+1层楼上前,必须先完成第i层。

如果奶牛被分配以最佳方式在楼层上工作,请计算完成谷仓的最小总时间。输出这个时间四舍五入到整数的结果;题目保证解答离两个整数之间的边界大于0.1。

输入格式

The first line of input contains NN and KK.

The next NN lines contain a1aNa_1 \ldots a_N, each a positive integer of size at most 101210^{12}.

第一行包括两个数N和K。

接下来N行包括了a[1]...a[n],每行一个不大于10^12的正整数。

输出格式

Please output the minimum time required to build the barn, rounded to the

nearest integer.

请输出完成谷仓的最小总时间(四舍五入至最接近的整数)。

2 5
10
4
5

提示

感谢 @ XY星系质量PK 的提供的翻译