Look Back(cf div3 905)

cf div3 905)"/>

Look Back(cf div3 905)

题意：给你一个长度为n（(1≤n≤10^5)数组a[]，你可以进行一个操作 使a[i]=a[i]*2,问最少经过多少次这样的操作使的a[]不递减,a[i]>=a[i-1]。

输入样例：

6

1

1

2

1 1

3

1 2 1

4

2 3 2 1

5

4 5 4 5 4

10

1 7 7 2 3 4 3 2 1 100

输出样例：  

1
1
4
7
4
28

思路： 要想使它非递减，肯定使遇到a[i-1]>a[i] 便让a[i-1]*2^x>=a[i] 最少乘x次使得a[i-1]>=a[i]

但是要考虑一个问题：遇到一个这样的就让a[i-1]*2^x 相应的也会影响后面的数乘多少个2 

如果都这样每一个暴力去乘去改变a[i-1]的值 N=1e5 数很大 若是最大可能 a[i]*2^N 会爆longlong

甚至会超时，这是就思考该怎么样去优化

采用前缀和的思想 用s[i]数组去计算 a[i]需要乘多少个2 不去实际改变a[i]的大小，而是用s[i]数组的方式记录下来每个数的达到符合要求的最小操作数

总的来说一共有两种情况

a[i]>=a[i-1]时

这时你要考虑 a[i]/2^t>=a[i-1] 可以用来抵消（前面的）乘2 从而使s[i]变小

s[i]=max(0,s[i-1]-t) s[i]最小就是0 就是不操作 前面的乘2改变的数 t都能抵消从而不改变值

a[i]<a[i-1]

例如：a[i-1]=2，a[i]=4，s[i-1]=3；

易得 t=1。a[i-1]*2*2*2=16，要使a[i]>=a[i-1]=16，那么a[i]需要乘 s[i-1]-t 个2，也就是2个2就可以满足a[i]>=16。

这时你要考虑 a[i-1]*2^t<=a[i] 此时这个a[i]一定要有相应的变化 最小变化就是乘2^t 如果前面也存在 a[j]<a[j-1]肯定也是乘2^x 这时相乘的2^y y肯定比t大了 要考虑全面 故s[i]=max(0,s[i-1]+t)

例如：a[i-1]=4，a[i]=2，s[i-1]=2；

易得 t=1。a[i-1]*2*2=16，要使a[i]>=a[i-1]=16，那么a[i]需要乘 s[i-1]+t 个2，也就是3个2就可以满足a[i]>=16。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N],s[N];
int main()
{int t;cin>>t;while(t--){int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];memset(s,0,sizeof s);for(int i=2;i<=n;i++){ll b=a[i-1],c=a[i];ll tt=0;if(b<c){while(b*2<=c){tt++;b*=2;	}s[i]=max((ll)0,s[i-1]-tt);}else {while(c<b){tt++;c*=2;}s[i]=max((ll)0,s[i-1]+tt);}}ll sum=0;for(int i=1;i<=n;i++) sum+=s[i];cout<<sum<<endl;}return 0;
}