题解：B4103 [CSP-X2023 山东] 代价

· · 题解

题目思路：

这道题乍一看很难，心想：“还是做别的吧”，其实仔细读完后还是挺简单的。算法主要考察的是对前缀和的使用。

用一个 s 来存计算的前缀和，一个 t 来计算代价， 公式前半部分是对代价的计算，后半部分是计算第二种的代价。最后求 res 和 t 的最小值即可。

AC code

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
int n, a, b, t , res = LLONG_MAX;
int x[100001], s[100001];
signed main()
{
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> a >> b;
  for(int i = 1; i <= n; i++){
      cin >> x[i];
  }
  sort(x + 1 ,x + 1 + n);

  //前缀和的计算
  for(int i = 1; i <= n; i++){
      s[i] = s[i-1] + x[i];
  }

  //结果部分
  for(int i = 1; i <= n; i++){
      t = ((i - 1) * x[i] - s[i - 1]) * a + (s[n] - s[i] - (n -  i) * x[i]) * b;
      res = min (res , t);
  }
  cout << res << endl;
  return 0;
}

最后感谢大佬@cxoi1711提供的思路。