#P1168. 2023.04.08-春招-第三题-玩具打包
2023.04.08-春招-第三题-玩具打包
![](https://s3.bmp.ovh/imgs/2024/09/03/9ec1757951030a02.jpg)
塔子哥开的玩具店生意越来越好,每天都有很多客人前来选购玩具。有一天,他接到了一个大单,客户想购买 n 个玩具,并且要求打包成多个玩具袋。塔子哥精心为客户挑选了 n 个玩具,并且将它们编号为 1,2,…,n。
然而,塔子哥发现这个订购单还有一个要求:每个玩具袋最多只能装 m 个玩具,并且同一个玩具袋里装的玩具编号必须是连续的。玩具袋的成本与容积成线性关系。
为了解决这个问题,他决定采用样本中点估计的方法来计算玩具袋的容积。具体来说,如果一个玩具袋中装的最大的玩具容积是 u,最小的是 v,那么这个玩具袋的成本就是 k×floor((u+v)/2)+s,其中 k 是玩具袋中装入玩具的个数,s 是一个常数, floor(x) 是下取整函数,比如 floor(3.8)=3 , floor(2)=2
客户并没有规定玩具袋的数量,但是希望玩具袋的成本越小越好,毕竟买玩具就很贵了。请求出塔子哥打包这 n 个玩具所用的最小花费。
第一行三个正整数 n,m,s 。意义如题面所示
第二行 n 个正整数 a1,a2,...,an ,表示每个玩具的体积。
对于全部数据, 1≤n≤104 , 1≤m≤103 , m≤n , 1≤ai,s≤104 。
输出一个整数,表示打包这 n 个玩具玩具袋的最小成本。
输入
6 4 3
1 4 5 1 4 1
输出
21
样例解释
前三个玩具装成一个玩具袋,后三个玩具装成一个玩具袋。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.