[Atcoder agc027 B] Garbage Collector

题目链接

Atcoder agc027 B

题目大意

现在有一条数轴,数轴上有$n$个点存在垃圾,有个捡垃圾的机器人从$0$号点出发,现在需要将所有垃圾运回$0$号点。
捡起一个垃圾需要消耗$X$能量,当身上有$k$个垃圾时,走一步需要消耗$(k+1)^2$能量。
回到起点倒一次垃圾也需要消耗$X$能量,注意这里倒垃圾时不管身上运载着多少垃圾,消耗能量均为$X$。
$n \le 2*10^5$

做法

感觉上很像$dp+$斜率优化。
但是这题有个非常关键的地方,每次出发所捡的垃圾并不一定相邻。
手动模拟一下,假设一次出发经过了$t_q,t_{q-1},t_{q-2}…t_1$点的话。
所需要的能量就是$X(q+1)+5t_1+5t_2+7t_3+9t_4…$
假设我们一共出发$A$次的话,那么最远的$2
A$个点会有$5$的贡献,再近一点的$A$个点有$7$的贡献,再近一点的$A$个点有$9$的贡献,以此类推。
最后再加上倒$A$次垃圾,捡$n$次垃圾的贡献$(A+n)*X$即可。
发现算这个贡献的复杂度其实是调和级数的,我们先预处理一下前缀和,暴力枚举$A$,暴力计算就好了。

代码

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
37
38
39
40
41
42
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (200005)
using namespace std;
int n,tt;
LL a[N],sum[N];
LL ans=9e18,x,now;
template <typename T> void read(T&t) {
t=0;
bool fl=true;
char p=getchar();
while (!isdigit(p)) {
if (p=='-') fl=false;
p=getchar();
}
do {
(t*=10)+=p-48;p=getchar();
}while (isdigit(p));
if (!fl) t=-t;
}
int main(){
read(n),read(x);
for (int i=1;i<=n;i++) read(a[i]),sum[i]=sum[i-1]+a[i];
for (int i=1;i<=n;i++){
now=x*(i+n);
tt=3;
for (int j=n;j>=1;j-=i){
if (tt==3) now+=(sum[j]-sum[max(0,j-i)])*5;
else now+=(sum[j]-sum[max(0,j-i)])*tt;
tt+=2;
if (now>=ans) break;
}
ans=min(ans,now);
}
printf("%lld",ans);
return 0;
}