本题是一道贪心题。

• 由样例解释我们可以看出本题是在模拟攻击公会的基础上再考虑如何移动攻城炮使得最后的贡献最小。只有攻城炮的位置会对答案产生影响，所以我我们对攻城炮的位置进行贪心，攻下第i城后攻城炮的位置有0-i种选择，数据范围(n<=2e5)，所以我们每轮循环算出攻下本城的贡献之后要算出将攻城炮移动到i位置和不移动的贡献大小，考虑前缀和,开始时pos=0，即题目所要求的的0位置。

• 不移动： ans1 = b * ((sum[n] - sum[i]) - x[pos] * (n -i));

• 移动： ans2 = a * (x[i] - x[pos]) + b * ((sum[n] - sum[i]) - x[i] * (n - i));

• 移动的答案记得加移动攻城炮对答案造成的贡献。
  

• 注意：本题的xi<=1e^8，但是在算贡献的时候会爆int，需要开long long（十年int十年空,不开long long见祖宗）

• 贪心的证明很简单：攻城炮移动造成的贡献小就移动，要不然不移动。由局部最优解上升到全局最优解。

• O(n)的时间复杂度即可顺利AC本题😄 。

• AC代码如下：

  #include <bits/stdc++.h>
  #define xx first
  #define yy second
  #define I __int128
  const int INF = 0x3f3f3f3f;
  const int N = 1e6 + 10;
  #define IOS                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
  using namespace std;
  typedef long long ll;
  typedef unsigned long long ull;
  typedef pair<int, int> PII;
  int xx[] = {0, 0, 1, -1};
  int yy[] = {1, -1, 0, 0};
  int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;  //求最大公约数
  }
  ll yinshu(ll x) {  //快速求一个数的因数个数
    ll ans = 0;
    for (ll i = 2; i <= sqrt(x); i++) {
      if (x % i == 0) ans += 2;
      if (i * i == x) ans--;
    }
    return ans;
  }
  ll sum[N];
  ll x[N];
  void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    int pos = 0;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
      cin >> x[i];
      sum[i] = sum[i - 1] + x[i];
    }
    for (int i = 1; i <= n; i++) {
      ans += b * (x[i] - x[pos]);  //攻城的价值
      //已经攻破，pos可选的位置是0-i,考虑贪心，每轮求最优解
      ll ans1 = b * ((sum[n] - sum[i]) - x[pos] * (n - i));  //不移动位置
      ll ans2 = a * (x[i] - x[pos]) + b * ((sum[n] - sum[i]) - x[i] * (n - i));
      //位置移动,就是攻城的价值+位置移动的价值
      if (ans2 < ans1) {
        ans += a * (x[i] - x[pos]);
        pos = i;
      }
    }
    cout << ans << endl;
  }
  int main() {
    IOS;
    int t;
    cin >> t;
    while (t--) {
      solve();
    }
  }