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;
}