SSL-OI夏日合宿 2020.08.22 A组

今天的题只改出来一道, 下午跟66炜打洛谷月赛去了. 思维题对我来说还是有点难, 可能确实没那个实力吧. 那么就先只写一题吧. (顺便把昨天没写完的题解也发了吧)

A 最佳解答

题意

给出$n$个数, 求出一个$x$, 使$\sum{\lfloor\frac{a_i}{x}\rfloor+a_i\ mod\ x}$. 特别的, 当 $x=1$, 值为$\sum{a_i}$.

$n\leq10^6$, $a_i\leq10^6$

故事

例行故事让我很没面子. 有一档$n^2$的数据我就把它做了, 可惜加了数据范围判断, 少拿了很多分. 赛后把判断去掉才发现, 这题数据竟然水到纯暴力能拿75?

题解

中午宿舍里北大爷才透露, 这就是一道暴力题, 稍加优化的暴力是能过的. 我们开个桶存下每个数的数量, 然后对这个桶做一遍后缀和. 我们发现, 如果枚举一个$x$的倍数, 将每个$x$的倍数位置上的值计算贡献的话: $[x,2x)$范围内会被计算一次, $[2x,3x)$范围内会被计算两次......

最后结果就是$\sum{a_i}-(x-1)\times res$, $res$是上面统计的贡献.

#define MXN (1000020)

#include <stdio.h>

#include <algorithm>

int n, a[MXN], mxa;
long long sum, res, ans;

int t[MXN];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif

    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]), sum += a[i], mxa = std::max(mxa, a[i]);

    if (n <= 1000 && mxa <= 2000) {  // Sub1
        ans = sum;
        for (int i = 2, j; i <= mxa; ++i) {
            for (res = j = 0; res < ans && j < n; ++j)
                res += (a[j] / i) + (a[j] % i);
            ans = std::min(ans, res);
        }
        printf("%lld", ans);
    } else {
        for (int i = 0; i < n; ++i)
            ++t[a[i]];
        for (int i = mxa; i >= 0; --i)
            t[i] += t[i + 1];
        ans = sum;
        for (int i = 2, j; i <= mxa; ++i) {
            for (res = sum, j = i; j <= mxa; j += i)
                res -= (i - 1) * t[j];
            ans = std::min(ans, res);
        }
        printf("%lld", ans);
    }

    return 0;
}