SSL-OI Summer Camp 2020.08.22 Group A

Today I only corrected one problem, and in the afternoon I went to play in the Luogu monthly contest with 66 Wei. Thinking problems are still a bit hard for me; maybe I really don't have the ability. So for now I'll just write one problem. (By the way, I'll also post the solution I didn't finish yesterday.)

A Best Answer

Problem Statement

Given $n$ numbers, find an $x$ such that $\sum{\lfloor\frac{a_i}{x}\rfloor+a_i\ mod\ x}$. In particular, when $x=1$, the value is $\sum{a_i}$.

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

Story

The routine story makes me lose face. There was a subtask with $n^2$ data and I did it, but unfortunately I added a data range check and lost a lot of points. After the contest, when I removed the check, I realized the data for this problem was so weak that pure brute force could get 75?

Solution

At noon in the dorm, the Peking University guy revealed that this is just a brute force problem, and a slightly optimized brute force can pass. We open a bucket to store the count of each number, then compute a suffix sum on this bucket. We find that if we enumerate multiples of an $x$, and calculate the contribution of the values at each multiple of $x$: the range $[x,2x)$ will be counted once, the range $[2x,3x)$ will be counted twice...

The final result is $\sum{a_i}-(x-1)\times res$, where $res$ is the contribution counted above.

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