2282. 贪心花店

1000ms 256MB 中等 贪心算法
题目描述
一群朋友(共 $k$ 人)要买 $n$ 朵花。花店老板规则:某人买第 $(x+1)$ 朵花时,价格为 $(x+1) \times {原始价格}$,其中 $x$ 是该人此前已购买的花的数量。 请计算购买所有花的最小总成本。
输入格式
- 第一行:两个整数 $n, k$ ($1 \le n, k \le 100$)。 - 第二行:$n$ 个整数 $c[i]$ ($1 \le c[i] \le 10^6$),表示每朵花的原始价格。
输出格式
- 一个整数,表示最小总成本。
样例 1
输入 (Input)
3 3
2 5 6
输出 (Output)
13
样例 2
输入 (Input)
3 2
2 5 6
输出 (Output)
15
样例 3
输入 (Input)
5 3
1 3 5 7 9
输出 (Output)
29
- $1 \le n, k \le 100$ - $1 \le c[i] \le 10^6$ **样例 1:$n=3, k=3, c=[2, 5, 6]$** * **分配方案**:因为有 3 个人要买 3 朵花,每个人只需要买一朵。 * **计算过程**: - 每个人都是第一次买花,倍率均为 $(0+1)=1$。 - 总价 = $2 \times 1 + 5 \times 1 + 6 \times 1 = 13$。 * **结论**:输出 **13**。 **样例 2:$n=3, k=2, c=[2, 5, 6]$** * **分配方案**:只有 2 个人买 3 朵花,必然有一人要买两朵。 * **计算过程**: 1. **第一轮**:两人分别买最贵的两朵($6$ 和 $5$),倍率为 1。花费:$6 \times 1 + 5 \times 1 = 11$。 2. **第二轮**:其中一人买剩下最便宜的一朵($2$),倍率变为 $(1+1)=2$。花费:$2 \times 2 = 4$。 3. **总计**:$11 + 4 = 15$。 * **结论**:输出 **15**。 **样例 3:复杂场景计算** * **逻辑展示**:该图展示了当购买数量较多时,价格 $9, 7, 5$ 的花在第一轮买(倍率 1),价格 $3, 1$ 的花在第二轮买(倍率 2)。 * **计算式**:$9 + 7 + 5 + 3 \times (1+1) + 1 \times (1+1) = 29$。
自测终端 stdin → stdout
输入 stdin
CtrlShiftEnter
输出 stdout

                
错误 stderr

                
CtrlEnter提交
自动保存已开启
操作成功
wzs_oj@kernel:~ — wzs-sh
guest@wzsoj:~$
刷新页面 F5
复制 Ctrl+C
粘贴 Ctrl+V
搜索题目
站点公告
今日神谕
CSP 倒计时
排行榜
我的提交
Esc 关闭 Enter 跳转 支持模糊匹配数字