文章目录
  1. 1. 题目描述
  2. 2. 输入格式
  3. 3. 输出格式
  4. 4. 样例一
    1. 4.1. input
    2. 4.2. output
    3. 4.3. explanation
  5. 5. 样例二
    1. 5.1. input
    2. 5.2. output
  6. 6. 样例三
  7. 7. 限制与约定
  8. 8. codes

题目描述

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

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

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

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

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

输入格式

第一行一个正整数 $n$,表示代码行数。

接下来 $n$ 行,第 $i$ 行一个正整数 $a_i$,为初始时第 $i$ 行缩进的空格个数。

输出格式

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

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

样例一

input


3
5
8
8


output


6

explanation

令默认TAB宽度为4即可。

样例二

input


10
2
3
5
7
11
13
17
19
23
29

output


45

样例三

见样例数据下载

限制与约定

测试点编号$n$的规模$a_i$的大小
1$n \leq 10^3$$a_i \leq 2000$
2
3$n \leq 10^5$$a_i \leq 2000$
4
5$n \leq 10^5$$a_i \leq 10^5$
6
7
8$n \leq 10^6$$a_i \leq 10^6$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

codes

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
33
34
35
36
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1000010;
int n;
ll arr[maxn];
ll s[maxn];
ll sum, end, ans;
int main()
{
scanf("%d", &n);
for(int i=0; i<n; i++)
{
scanf("%lld", arr+i);
s[arr[i]]++;
sum+=arr[i];
end= max(end, arr[i]);
}
for(ll i=end-1; i>=0; i--)
s[i]+=s[i+1];
for(ll i=1; i<=end; i++)
{
ll cur=0;
for(ll j=i; j<=end; j+=i)
cur+=s[j];
cur*=(i-1);
ans=max(cur, ans);
}
printf("%lld\n", sum-ans);
return 0;
}
文章目录
  1. 1. 题目描述
  2. 2. 输入格式
  3. 3. 输出格式
  4. 4. 样例一
    1. 4.1. input
    2. 4.2. output
    3. 4.3. explanation
  5. 5. 样例二
    1. 5.1. input
    2. 5.2. output
  6. 6. 样例三
  7. 7. 限制与约定
  8. 8. codes