神题啊……

考虑让答案最小不好做，那么我们想，把连续的一段空格变成一个TAB（假设TAB长度为\(x\)）就是减少\(x - 1\)空格，那么我们尝试去最大化减小的空格的量。

然后考虑枚举\(x\)是啥，然后去算减少的空格的量。对于任意\(a_i\)，减少的空格量就是\((x-1)\lfloor\frac{a_i}{x}\rfloor\)，这似乎可以整除分块哎……

但是会被T掉。我们想，其实我们对任意\(x\)，我们去枚举\(\lfloor\frac{a_i}{x}\rfloor\)就行啦，要查询满足条件的\(a_i\)数量可以预处理一个权值前缀和然后就能\(O(1)\)做啦、

假设\(X = \max\{a_i\}\)，那么每一个\(x\)对时间复杂度的贡献就是\(O(\frac{X}{x})\)。这不就是调和级数吗？所以时间复杂度事\(O(X\ln X)\)。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
const int maxn = 1000005;
typedef long long ll;
int a[maxn], C[maxn];
int n, bd;
void process() {
  for(int i = 1; i <= n; i ++) {
    C[a[i]] ++;
  }
  for(int i = 1; i <= bd; i ++) {
    C[i] += C[i - 1];
  }
}
ll sum;
ll query(int x, int p) {
  int l = x * p;
  int r = x * (p + 1) - 1;
  if(r > bd) r = bd;
  return (C[r] - C[l - 1]);
}
ll calc(int x) {
  ll delta = 0;
  for(int i = 1; i <= (bd / x); i ++) {
    ll cnt = query(x, i);
    delta += (ll(i)) * cnt * (ll(x - 1));
  }
#ifdef LOCAL
  printf("ans of %d : %lld\n", x, sum - delta);
#endif
  return (sum - delta);
}

int main() {
  scanf("%d", &n);
  sum = 0LL; bd = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &a[i]);
    bd = std::max(bd, a[i]);
    sum += a[i];
  }
  process();
  ll ans = sum;
  for(int i = 1; i <= bd; i ++) {
    ans = std::min(ans, calc(i));
  }
  printf("%lld\n", ans);
  return 0;
}

• 相关文章
• 全局相关文章