B. Minimal Cost
题面：
B. Minimal Cost
There is a graph of n rows and 106+2 columns, where rows are numbered from 1 to n and columns from 0 to 106+1:
Let's denote the node in the row i and column j by (i,j).
Initially for each i the i-th row has exactly one obstacle — at node (i,ai). You want to move some obstacles so that you can reach node (n,106+1) from node (1,0) by moving through edges of this graph (you can't pass through obstacles). Moving one obstacle to an adjacent by edge free node costs u or v coins, as below:
If there is an obstacle in the node (i,j), you can use u coins to move it to (i−1,j) or (i+1,j), if such node exists and if there is no obstacle in that node currently.
If there is an obstacle in the node (i,j), you can use v coins to move it to (i,j−1) or (i,j+1), if such node exists and if there is no obstacle in that node currently.
Note that you can't move obstacles outside the grid. For example, you can't move an obstacle from (1,1) to (0,1).
Refer to the picture above for a better understanding.
Now you need to calculate the minimal number of coins you need to spend to be able to reach node (n,106+1) from node (1,0) by moving through edges of this graph without passing through obstacles.
Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.
The first line of each test case contains three integers n, u and v (2≤n≤100, 1≤u,v≤109) — the number of rows in the graph and the numbers of coins needed to move vertically and horizontally respectively.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤106) — where ai represents that the obstacle in the i-th row is in node (i,ai).
It's guaranteed that the sum of n over all test cases doesn't exceed 2⋅104.
Output
For each test case, output a single integer — the minimal number of coins you need to spend to be able to reach node (n,106+1) from node (1,0) by moving through edges of this graph without passing through obstacles.
It can be shown that under the constraints of the problem there is always a way to make such a trip possible.
Example
inputCopy
3
2 3 4
2 2
2 3 4
3 2
2 4 3
3 2
outputCopy
7
3
3
解题步骤：
提醒：障碍物不会放到第(0)列和第(10^6+1)列
然后观察一下图形，会发现障碍物一共有三种排列情况：
一、障碍物全在一列上，即所有障碍物之间的距离之差的所有绝对值中的最大值为(0)
二、障碍物之间的距离之差的所有绝对值中的最大值为(1)，这种情况如下图：
三、障碍物之间的距离之差的所有绝对值中的最大值大于等于(2)，这种情况如下图：
对于第一种情况：可以看出只需将任意障碍物横向平移两个单位
对于第二种情况：横移或者纵移一个单位都是可以的，分为两种情形
1、第一种情形是(u≥v)，这样就是纵着移，答案为(v)。
2、第二种情形是(u<v)，这样就是横着一，答案为(u)。
对于第三种情况：看图，不需要移动任何的障碍物，所以答案为(0)。
代码如下，三种情况的位置都会在注释中标注出来
#include <iostream>
#include <cmath>
using namespace std;
int main ( void )
{
int T;
cin >> T;
while ( T-- )
{
int n, u, v, d = -1; // d 是每个障碍物的距离绝对值的最大值，初始化为最小值 -1
cin >> n >> u >> v;
int a;
cin >> a;
for ( int i = 1; i < n; i++ ) // 因为前面已经读取了一个a，所以这里i从0开始
{
int b;
cin >> b;
d = max ( d, abs ( a - b ) ); // 在这里更新 d，有看不懂的地方可以私信或留言哦
a = b; // b在下一轮循环中充当a
}
if ( d == 0 ) /* 第一种情况 */
{
if ( v < u ) cout << 2 * v << endl;
else cout << u + v << endl;
} else if ( d == 1 ) {
if ( v < u ) cout << v << endl; /* 第二种情况第一种情形 */
else cout << u << endl; /* 第二种情况第二种情形 */
} else
cout << 0 << endl; /* 第三种情况 */
}
return 0;
}
over~