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;
}
当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »