UOJ21 【UR #1】缩进优化题解

题意：

小 O 是一个热爱短代码的选手。在缩代码方面，他是一位身经百战的老手。世界各地的 OJ 上，很多题的最短解答排行榜都有他的身影。这令他感到十分愉悦。

最近，他突然发现，很多时候自己的程序明明看起来比别人的更短，实际代码量却更长。这令他感到很费解。经过一番研究，原来是因为他每一行的缩进都全是由空格组成的，大量的空格让代码量随之增大。

现在设小 O 有一份 $n$ 行的代码，第 $i$ 行有 $a_i$ 个空格作为缩进。

为解决这一问题，小 O 要给自己文本编辑器设定一个正整数的默认 Tab 宽度 $x$，然后对于每一行，编辑器从头至尾不断把连续 $x$ 个空格替换成一个 Tab，直到剩余空格数不足 $x$ 个。

最终缩进所占代码量为空格数与 Tab 数的和。请你帮小 O 选择一个合适的 $x$ ，使得缩进所占代码量最小。

输入格式：

第一行包含一个正整数 $n(n \leq 10^6)$，表示代码行数。

接下来 $n$ 行，第 $i$ 行包含一个正整数 $a_i(a_i \leq 10^6)$，为初始时第 $i$ 行缩进的空格个数。

输出格式：

输出一行一个整数，表示缩进所占代码量最小是多少。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

关键词：调和级数

简单推推柿子可以发现，我们要求的是下面这个东西的最小值

$\sum_{i=1}^{n} \left\lfloor\dfrac{a_i}{T}\right\rfloor + \sum_{i=1}^{n} \left(a_i \bmod T\right)$

根据常见套路 $a_i \bmod T = a_i - T\left\lfloor{\frac{a_i}{T}}\right\rfloor$，有

$\sum_{i=1}^{n} a_i-(T-1)\sum_{i=1}^{n}\left\lfloor\dfrac{a_i}{T}\right\rfloor$

显然前面是不变的，要最大化 $(T-1)\sum_{i=1}^{n}\left\lfloor\frac{a_i}{T}\right\rfloor$

显然 $T \in \left[1,\max\{a_i\}\right]$ ，考虑枚举 $T$ 。

注意到 $\left\lfloor\frac{a_i}{T}\right\rfloor$ 只有至多 $\left\lfloor\frac{\max\{a_i\}}{T}\right\rfloor$ 种取值，即

$\forall a_i \in [kT-T,kT-1],~\left\lfloor\frac{a_i}{T}\right\rfloor=k-1\quad 1 \le k \le \left\lfloor\frac{\max\{a_i\}}{T}\right\rfloor \land k \in \mathbb{N}$

比如 $\forall a_i \in [T,2T-1],~\left\lfloor\frac{a_i}{T}\right\rfloor=1$ 。

暴力处理所有的区间 $[kT-T,kT-1]$ ，然后看看每一段区间里面有多少个 $a_i$ 。

然后分析一下时间复杂度。记 $M=\max\{a_i\}$ 。

对于每个枚举的 $T$ ，区间个数为 $\left\lfloor\frac{M}{T}\right\rfloor$ ，则

$M + \frac{M}{2} + \frac{M}{3} + \cdots + \frac{M}{M} = M\sum_{x=1}^{M}x^{-1} = \Theta(M \ln M)$

这就是调和级数。不过其实 $T=1$ 的情况不枚举也无所谓（

故时间复杂度 $O(M \log M)$（更精确点就是 $\Theta(M \ln M)$ 啦）

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e6+15))

int n,T,res,tmp,sum[N];
int calc(int l,int r)
{
    return (r > T ? sum[T] : sum[r]) - (l ? sum[l-1] : 0);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,x; i<=n; i++)
        cin >> x, res+=x, T=max(T,x),++sum[x];
    for(int i=1; i<=T; i++) sum[i] += sum[i-1];
    for(int i=2; i<=T; i++)
    {
        int cur=0;
        for(int cnt=0, l=0, r=i-1; l<=T; l+=i, r+=i, ++cnt)
            cur += calc(l,r) * cnt;
        if(cur * (i-1) > tmp) tmp = cur * (i-1);
    }
    cout << (res - tmp) << '\n';
    return 0;
}