104 lines
1.6 KiB
Markdown
104 lines
1.6 KiB
Markdown
# CF1355E Restorer Distance
|
||
|
||
## 题目描述
|
||
|
||
你需要修复一堵墙。这堵墙由 $N$ 根砖柱组成，第 $i$ 根柱子的初始高度为 $h_{i}$，高度以砖块数计。修复后，所有 $N$ 根柱子的高度都应相等。
|
||
|
||
你可以进行以下操作：
|
||
|
||
- 在一根柱子顶部放一块砖，操作费用为 $A$；
|
||
- 从一根非空柱子的顶部移除一块砖，操作费用为 $R$；
|
||
- 将一根非空柱子顶部的一块砖移动到另一根柱子的顶部，操作费用为 $M$。
|
||
|
||
你不能新建柱子，也不能忽略已有的柱子，即使它们的高度变为 $0$。
|
||
|
||
请问修复这堵墙的最小总费用是多少？换句话说，使所有柱子的高度相等的最小总费用是多少？
|
||
|
||
## 输入格式
|
||
|
||
输入的第一行包含四个整数 $N$、$A$、$R$、$M$（$1 \le N \le 10^{5}$，$0 \le A, R, M \le 10^{4}$），分别表示柱子的数量和三种操作的费用。
|
||
|
||
第二行包含 $N$ 个整数 $h_{i}$（$0 \le h_{i} \le 10^{9}$），表示每根柱子的初始高度。
|
||
|
||
## 输出格式
|
||
|
||
输出一个整数，表示修复墙体的最小总费用。
|
||
|
||
## 输入输出样例 #1
|
||
|
||
### 输入 #1
|
||
|
||
```
|
||
3 1 100 100
|
||
1 3 8
|
||
```
|
||
|
||
### 输出 #1
|
||
|
||
```
|
||
12
|
||
```
|
||
|
||
## 输入输出样例 #2
|
||
|
||
### 输入 #2
|
||
|
||
```
|
||
3 100 1 100
|
||
1 3 8
|
||
```
|
||
|
||
### 输出 #2
|
||
|
||
```
|
||
9
|
||
```
|
||
|
||
## 输入输出样例 #3
|
||
|
||
### 输入 #3
|
||
|
||
```
|
||
3 100 100 1
|
||
1 3 8
|
||
```
|
||
|
||
### 输出 #3
|
||
|
||
```
|
||
4
|
||
```
|
||
|
||
## 输入输出样例 #4
|
||
|
||
### 输入 #4
|
||
|
||
```
|
||
5 1 2 4
|
||
5 5 3 6 5
|
||
```
|
||
|
||
### 输出 #4
|
||
|
||
```
|
||
4
|
||
```
|
||
|
||
## 输入输出样例 #5
|
||
|
||
### 输入 #5
|
||
|
||
```
|
||
5 1 2 2
|
||
5 5 3 6 5
|
||
```
|
||
|
||
### 输出 #5
|
||
|
||
```
|
||
3
|
||
```
|
||
|
||
## 说明/提示
|
||
|
||
由 ChatGPT 4.1 翻译 |