CF1883E Look Back

One_JuRuo · 2023-10-27 22:59:10 · 题解

思路

首先，对于 a_i 他必须得不小于最后的 a_{i-1}，所以每个数乘的次数都是固定的。

如果暴力去乘 2 直到不小于为止，将会超时，所以考虑使用其他的方法进行优化。

因为前后两个数可以同时乘以 2，相对比值不会变化，所以我们可以考虑对于最开始的 a_{i-1},a_i 直接计算需要多少次才能使 a_i 不小于 a_{i-1}，也就是两者需要乘以 2 的差值，那么这个差值加上 a_{i-1} 需要乘以 2 的次数，就是 a_i 需要的次数，只要把每两个数之间的差值都算出来，也就是次数的差分，再求一遍前缀和，就可以得到每个数需要的次数，再求一遍前缀和就是次数的总和。

不过需要注意的是，一个数差分后的次数可以是负数，代表这个数比前面一个数可以少乘以几次 2，同时前缀和不能是负数，因为你不能除以 2，所以需要与 0 取个 \max。

AC code

#include<bits/stdc++.h>
using namespace std;
long long T,n,a,la,ans,c1,c2,sum;
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&la),ans=sum=0;
        for(int i=1;i<n;++i)
        {
            scanf("%lld",&a),c1=0,c2=0;
            int l=la,r=a;
            while(l<r) l<<=1,++c1;//少乘几个2
            while(l>r) r<<=1,++c2;//多乘几个2
        /*c2-c1就是综合需要多乘几个2*/
            sum+=c2-c1,sum=max(0ll,sum),ans+=sum,la=a;
        }
        printf("%lld\n",ans);
    }
    return 0;
}