[Atcoder agc027 B] Garbage Collector

Posted on | In , | Views:

题目链接

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$次的话，那么最远的$2A$个点会有$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;
}