AGC027B

WitheredZeal · 2021-10-11 17:25:56 · 题解

题意

一个数轴上有 n 个垃圾，它们的位置分别为 x_1,x_2,…,x_n(0<x_1<x_2<…<x_n\le10^9)，有一个机器人开始时在位置 0 上，它每个时刻可以选择左右移动或者捡起一个垃圾，当它回到位置 0 时可以把手上的垃圾都扔掉。

当机器人手上有 k 个垃圾时，走 1 的距离需要消耗的 (k+1)^2 的能量，机器人单次捡垃圾或者丢垃圾都需要 x 的能量。

求机器人把所有垃圾都扔到垃圾桶里最少需要多少能量。

题解

首先假设我们从位置 0 出发一次性捡了 m 个垃圾，位置分别是 p_1,p_2 \cdots p_m。
显然最优方案是，先走到 p_m，然后往前走，经过一个垃圾就捡起来。

简要证明：考虑每段 p_i \to p_{i+1} 和 p_{i+1} \to p_i，一定至少经过 2 次，而 p_{i+1} \to p_i 的最后一次经过时，手上一定至少有 i+1 及后面的所有垃圾，因此该方法是下界。

观察一下它走的每段路程的权值，以 m=5 为例：

黄色的即为多出来需要走的路的权值。
实际上是 6p_1 + 4p_2 + 2p_3，即为 2\sum _{i=1}^{m-2}i p_{m-1-i}

现在假设我们已经确定了，我们总共只丢了 k 次垃圾，那么少用的 x 已经确定了，我们需要最小化我们多走的能量。
可以证明，答案就是，将下标模 k 同余的垃圾都分为一组，然后一次性拿掉。

简要证明：考虑我们一定试图让下标考后的坐标，系数尽量小。因此从后往前的系数应该依次为 2k 个 0，k 个 2，k 个 4……

我们枚举 k 就能得到一个 O(n^2) 的做法了，要是在正式比赛中就能获得 400 分的好成绩了！

部分分代码：

int n,X,ans,res;
int x[N];
signed main()
{
    rd(n);rd(X);res=inf;ans=n*X;
    for (int i=1;i<=n;i++) rd(x[i]),ans+=5*x[i];
    reverse(x+1,x+n+1);
    for (int k=1;k<=n;k++)
    {
        int tmp=k*X;
        for (int i=1;i<=n;i++) tmp+=2*max((i-1)/k-1,0LL)*x[i];
        res=min(res,tmp);
    }
    cout<<ans+res<<endl;
}

这个做法太拉了，我们要试图去优化它。

我们观察上面部分分的代码，里面有这么一个东西：
for (int i=1;i<=n;i++) tmp+=2*max((i-1)/k-1,0LL)*x[i];
但是我们想，所有的 \lfloor \frac i k \rfloor 是不是总共只会变化不超过 O(n \sqrt n) 次？
那么我们当 k 改变的时候，直接继承上一次的答案，再把需要改变的给改变了，是不是就行了？

总复杂度 O(n \sqrt n)。

然而，直接这么写似乎被卡常了。

我们来试图优化一下常数：

我们求分成 k 组时 tmp-kX。
将 x 数组 reverse 后，有它 =2 \sum _{i=1}^n \max(\lfloor \frac {i-1} k \rfloor-1,0) x_i = 2(\sum _{i=1}^n \lfloor \frac {i-1} k \rfloor x_i - \sum _{i=k+1}^n x_i)
我们需要干的就是快速求出 t_k =\sum _{i=1}^n \lfloor \frac{i-1} k \rfloor x_i。

我们不放入 vector 里面，而是差分后直接算，这样常数会小一点。

然而它 WA 了。

为什么会 WA 呢，我们把第 13 个测试点下载下来看看，本地开 -fsanitize=undefined 运行一下。

runtime error: signed integer overflow: 135806551569375 + 9223312156527645800 cannot be represented in type 'long long int'

居然爆 long long 了，被埋伏了一手。

我们可以用 __int128，但是这样可能就会因为常数太大而过不去了。

毛咕咕一下，发现这种情况下 k 不可能很小，那么特判一下就过了。

严谨的下界不是很好估计，下面这份代码能 AC 但是可以叉掉。

int n,X;
long long ans,res;
int x[N],a[N];
long long s[N],t[N];
signed main()
{
    rd(n);rd(X);res=inf;ans=1ll*n*X;
    for (int i=1;i<=n;i++) rd(x[i]),ans+=5ll*x[i];
    reverse(x+1,x+n+1);
    for (int i=0;i<n;i++) for (int j=1;j<=i;j=(i/(i/j))+1) if (n<=3000 || j>=10) t[j]+=1ll*i/j*x[i+1],t[i/(i/j)+1]-=1ll*i/j*x[i+1];
    for (int i=1;i<=n;i++) t[i]+=t[i-1];
    for (int i=1;i<=n;i++) s[i]=s[i-1]+x[i];
    for (int k=1;k<=n;k++)
    {
        if (n>3000 && k<10) continue;
        long long tmp=1ll*k*X+2ll*(t[k]-(s[n]-s[k]));
        res=min(res,tmp);
    }
    cout<<ans+res<<endl;
}

但是上面这个做法还是不够优秀，我们还可以继续优化。

实际上这个做法应该比上面那个做法更简单，是我菜了。

我们可以直接计算 t_k 的。

回忆一下：t_k =\sum _{i=1}^n \lfloor \frac{i-1} k \rfloor x_i。
这个 \lfloor \frac {i-1} k\rfloor 只有 \lfloor \frac n k\rfloor 种取值，我们可以枚举它，然后相当于算一段区间的和。
前缀和优化之后复杂度是调和级数 O(n \log n)。

__int128 n,X;
__int128 ans,res;
__int128 x[N],a[N];
__int128 s[N*2],t[N];
signed main()
{
    rd(n);rd(X);res=inf;ans=1ll*n*X;
    for (__int128 i=1;i<=n;i++) rd(x[i]),ans+=5ll*x[i];
    reverse(x+1,x+n+1);
    for (__int128 i=1;i<=n;i++) s[i]=s[i-1]+x[i];
    for (__int128 k=1;k<=n;k++)
    {
        for (__int128 i=1;i<=n/k;i++) t[k]+=i*(s[min(1ll*i*k+k,1ll*n)]-s[i*k]);
        __int128 tmp=1ll*k*X+2ll*(t[k]-(s[n]-s[k]));
        res=min(res,tmp);
    }
    wt(ans+res);
}