题目描述

给定一个长度为 \(N\) 的数组 \(A\)，每次你可以令 \(A_i \leftarrow A_i+1\) 或 \(A_i-1\)。求进行至多 \(k\) 次操作后 \(A\) 中最少不同元素数量。

思路

首先对 \(A\) 进行排序。

令 \(dp_{i,j}\) 表示考虑前 \(i\) 个数，有 \(j\) 个不同的值时最多还能剩余几次操作。

很明显有 \(dp_{i,j}=\max \limits_{1\le l\le x\le i} \{dp_{l-1,j-1}+sum_i - sum_{x}-(i-x)\cdot A_x + (x - l)\cdot A_x - sum_{x-1}+sum_l\}\)。

这个式子中似乎只能优化 \(x\)，所以我们考虑怎么优化。

这里的 \(x\) 实际上就是在枚举变成哪个值，假设一开始我们不用下标而用值来表示。每次令 \(x\leftarrow x+1\)，这样做会使答案 \(+\le x的个数-> x的个数\)，一开始这个增量是负的，逐渐变大。而当增量 \(=0\) 时也就是最小值。

而哪个地方 \(=0\) 呢？此时 \(\le x的个数=> x的个数\)，也就是在 \(\lceil \frac{l+i}{2} \rceil\) 处。

空间复杂度 \(O(N^2)\)，时间复杂度 \(O(N^3)\)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 301;

int T, n, a[MAXN], ans;
ll k, sum[MAXN], dp[MAXN][MAXN];

void Solve() {
  cin >> n >> k;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1);
  for(int i = 1; i <= n; ++i) {
    sum[i] = sum[i - 1] + a[i];
  }
  for(int i = 0; i <= n; ++i) {
    for(int j = 0; j <= n; ++j) {
      dp[i][j] = -1;
    }
  }
  dp[0][0] = k;
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
      for(int l = 1; l <= i; ++l) {
        dp[i][j] = max(dp[i][j], dp[l - 1][j - 1] + sum[(l + i + 1) / 2] + 1ll * a[(l + i + 1) / 2] * (i - (l + i + 1) / 2) - 1ll * a[(l + i + 1) / 2] * ((l + i + 1) / 2 - l) + sum[(l + i + 1) / 2 - 1] - sum[l - 1] - sum[i]);
      }
    }
  }
  for(int i = 1; i <= n; ++i) {
    if(dp[n][i] >= 0) {
      cout << i << "\n";
      return;
    }
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for(cin >> T; T--; Solve()) {
  }
  return 0;
}