数字魔法

去年新生赛预选题目 赛时没做出来
最小代价其实就是全部变到中位数 但是这样需要排序 因为本身数组不一定有序 那么此时就陷入僵局了
但是题目给了一个条件特别重要 1 <= a[i] <= 100
也就是说我最终要变到的中位数的值一定属于[1,100]
所以我可以预先处理a[i]的前n项全部变到[1,100]之间的任意一个值所需要的总魔力值 用数组b[i][j]记录，i是目标魔力值 j是数组的项数 这样就转变成了一个前缀和问题 我只需要每次枚举1~100 每次更新ans = ( ans, b[i][r] - b[i][l - 1] ) 即可获得最终答案

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[110][N];
int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, m;cin >> n >> m;
  for (int i = 1;i <= n; ++ i) cin >> a[i];
  for (int i = 1;i <= 100; ++ i) {
    for (int j = 1;j <= n; ++ j) {
      // 将前j项变化到i所需花费的魔力值
      b[i][j] = b[i][j - 1] + abs(a[j] - i);
    }
  }
  while (m--) {
    int l, r;cin >> l >> r;
    int ans = 2e9;
    for (int i = 1;i <= 100; ++ i) {
      ans = min(ans, b[i][r] - b[i][l - 1]);
    }
    cout << ans << '\n';
  }
}

对于这样的前缀和 需要多加注意