最佳解答
最佳解答 \operatorname{最佳解答} 最佳解答
题目链接: l u o g u T 145120 luogu\ T145120 luogu T145120 / S S L 比 赛 1510 SSL比赛\ 1510 SSL比赛 1510
题目
输入
输出
样例输入
3
5
8
8
样例输出
6
样例数据
TAB 的长度为 4 4 4 的时候,答案是 1 + ( 5 − 4 ) + 2 + ( 8 − 8 ) + 2 + ( 8 − 8 ) = 6 1+(5-4)+2+(8-8)+2+(8-8)=6 1+(5−4)+2+(8−8)+2+(8−8)=6
数据范围
大数据
思路
这道题是一道数学题,不过可以用三分来做。
我这里讲数学方法,三分的博客等我们这里有人做出来,我把链接贴在这里。
% % % F Y 大 佬 的 三 分 做 法 链 接 % % % \%\%\% FY 大佬的三分做法链接\%\%\% %%%FY大佬的三分做法链接%%%
我就化公式:(这里的除号都是整除,
m
i
n
(
)
min()
min() 就是枚举
x
x
x 然后统计最小值)
(不太会写公式,见谅)
m
i
n
(
∑
i
=
1
n
(
(
a
i
/
x
)
+
(
a
i
%
x
)
)
)
min(\sum\limits_{i=1}^{n}((a_i/x)+(a_i\%x)))
min(i=1∑n((ai/x)+(ai%x)))
m
i
n
(
∑
i
=
1
n
(
(
a
i
/
x
)
+
(
a
i
−
a
i
/
x
×
x
)
)
)
min(\sum\limits_{i=1}^{n}((a_i/x)+(a_i-a_i/x\times x)))
min(i=1∑n((ai/x)+(ai−ai/x×x)))
m
i
n
(
∑
i
=
1
n
(
a
i
/
x
+
a
i
−
a
i
/
x
×
x
)
)
min(\sum\limits_{i=1}^{n}(a_i/x+a_i-a_i/x\times x))
min(i=1∑n(ai/x+ai−ai/x×x))
m
i
n
(
∑
i
=
1
n
(
a
i
−
a
i
/
x
×
(
x
−
1
)
)
)
min(\sum\limits_{i=1}^{n}(a_i-a_i/x\times (x-1)))
min(i=1∑n(ai−ai/x×(x−1)))
m
i
n
(
∑
i
=
1
n
a
i
−
∑
i
=
1
n
(
a
i
/
x
×
(
x
−
1
)
)
)
min(\sum\limits_{i=1}^{n}a_i-\sum\limits_{i=1}^{n}(a_i/x\times (x-1)))
min(i=1∑nai−i=1∑n(ai/x×(x−1)))
m
i
n
(
∑
i
=
1
n
a
i
−
∑
i
=
1
n
(
a
i
/
x
)
×
(
x
−
1
)
)
min(\sum\limits_{i=1}^{n}a_i-\sum\limits_{i=1}^{n}(a_i/x)\times (x-1))
min(i=1∑nai−i=1∑n(ai/x)×(x−1))
∑
i
=
1
n
a
i
\sum\limits_{i=1}^{n}a_i
i=1∑nai 可以预处理,但是
∑
i
=
1
n
(
a
i
/
x
)
\sum\limits_{i=1}^{n}(a_i/x)
i=1∑n(ai/x) 怎么办呢?
我们有一种方法:
我们预处理出大于等于
i
i
i 的数有多少个,我这里用
b
[
i
]
b[i]
b[i] 来存。
然后我们枚举当前枚举的
x
x
x 的倍数,看有多少个数超过了
x
x
x 的这个倍数,加进一个数组里面。最后这个数组里面存的数就是答案了。
为什么呢?
因为我们可以发现,如果
a
/
x
=
b
a / x = b
a/x=b ,那它其实就对答案贡献了
b
b
b 次,那其实就是答案咯。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
#define rr register
using namespace std;
ll n, a[1000001], xr, sum, ans, tmp[1];
ll b[1000001];
ll read() {//快读
ll an = 0, zhengfu = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') zhengfu = -zhengfu;
c = getchar();
}
while (c >= '0' && c <= '9') {
an = an * 10 + c - '0';
c = getchar();
}
return an * zhengfu;
}
int main() {
// freopen("text.txt", "r", stdin);
memset(tmp, 0x7f, sizeof(tmp));//初始化
ans = tmp[0];
n = read();//读入
for (rr ll i = 1; i <= n; i++) {
a[i] = read();//读入
sum += a[i];//求出a[i]的和
b[a[i]]++;//记录
xr = max(xr, a[i]);//求出最大值
}
for (rr ll i = xr - 1; i >= 1; i--)//求出有多少个大于i的数,用b[i]储存
b[i] += b[i + 1];
for (rr ll i = 1; i <= xr; i++) {//枚举x
ll now = sum;
ll minus = 0;
for (rr ll j = i; j <= xr; j += i)//算公式
minus = minus + b[j];
now -= minus * (i - 1);
ans = min(ans, now);//找到答案最小的那个
}
printf("%lld", ans);//输出
return 0;
}