CF1883E Look Back

思路

首先，对于 \(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;
}