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
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功