边打边移的作用：移动后，攻击后续每个位置的攻击距离变短

但是攻击花费变少的同时移动的花费要变多

所以我的做法是计算每个点：假如攻城炮最终移动到这个点，我们的总花费是多少

然后比较出最小花费

然后就要想，假如我们要移动到这个位置，花费怎么算好算呢

我们很容易想到，要移动到某个点，一定是边打边移动花费最小，如果一直打到那个点再移动过去是比较亏的

变打边移动的话，移动的花费就是b*该点的位置

而这个点以前的攻击花费就是a该点位置（假如移到a3点,攻击距离=（a1-0+a2-a1+a3-a2）=a3），该点以后的攻击总距离=a4-a3+a5-a3+a6-a3+...+an-a3=(a4+a5+a6+...+an)-(a3(n-3)),而a4+a5+...+an=总前缀和-(a1+a2+a3)=总前缀和-第三个点的前缀和

OK，上代码：

#include<stdio.h>

int x[200000];
long long y[200000];

int main()
{
    int t;
    scanf("%d",&t);
    long long n,a,b;
    int i;
    long long num,num2,ans;
    while(t--)
    {
        num=0;
        scanf("%lld %lld %lld",&n,&a,&b);
        for(i=0;i<n;i++)
        {
            scanf("%d",&x[i]);
            num+=x[i];
            y[i]=num;//记录每个点的前缀和
        }
        ans=num*b;
        for(i=0;i<n-1;i++)
        {
            num2=(x[i]+num-y[i]-(n-i-1)*x[i])*b+x[i]*a;
//计算如果最终移动到当前点位，移动和攻击的总花费是多少
//x[i]为该点之前的总攻击距离，num为总前缀和，y[i]为该点的前缀和
//n-i-1为该点之后攻击的次数，因为每次攻击都要少一个x[i]的攻击距离
            if(num2<ans)ans=num2;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

原题连接：Problem - C - Codeforces

本题的核心需要考虑： 每次攻破敌对公会以后是否需要更换攻城炮的的位置？

只需要比较一下：更换位置的花费和更换后可以减少占领后续公会的花费进行比较，如果前者大就不换，后者大就换，这样总花费是最小的。

我们需要先预处理出 $x_i$的前缀和。

更换位置的花费: 假如是从第 $p r e$ 个公会位置占领到第 $i$ 个公会， $w 1 = a b s ( c [ i ] − c [ p r e ] ) ∗ a$

假如更换以后可以减少占领后续公会的花费：$w 2 = ( n − i ) ∗ b ∗ ( c [ i ] − c [ p r e ] )$

只要比较这两个的花费然后选择方案即可。

本题是一道贪心题。

• 由样例解释我们可以看出本题是在模拟攻击公会的基础上再考虑如何移动攻城炮使得最后的贡献最小。只有攻城炮的位置会对答案产生影响，所以我我们对攻城炮的位置进行贪心，攻下第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();
    }
  }