DDOSvoid's Blog

Uoj 21【UR-1】缩进优化

发表于 分类于
本文字数： 872 阅读时长 ≈ 1 分钟

题目描述

https://uoj.ac/problem/21

Solution

答案为 $\sum_{i=1}^n a_i-(k-1)\sum_{i=1}^n\lfloor \frac{a_i}{k}\rfloor$ 其中 $k$ 是选定的缩进宽度

首先考虑数论分块，枚举 $k$，这样的时间复杂度为 $O(n\sqrt n)$

注意到既然要枚举所有 $k$，我们不如反过来算，即考虑 $\lfloor \frac{x}{k}\rfloor$ 相同的一段 $x$

那么我们只需要知道这一段 $x$ 中有多少 $a$ 即可

时间复杂度为 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#define maxn 1000010
#define INF 1000000000000000
#define ll long long
using namespace std;

int n, m, a[maxn], s[maxn];

ll sum;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i]; ++s[a[i]];
        m = max(a[i], m), sum += a[i];
    }
    for (int i = 1; i <= m; ++i) s[i] += s[i - 1];
    ll ans = 0;
    for (int i = 2; i <= m; ++i) {
        ll sum = 0; 
        for (int j = i, k = 1; j <= m; j += i, ++k) 
            sum += (ll) (s[min(m, j + i - 1)] - s[j - 1]) * k * (i - 1);
        ans = max(ans, sum); 
    }
    cout << sum - ans << "\n";
    return 0;
}