CodeForces 1883E Look Back

题目链接：CodeForces 1883E【Look Back】

思路

       若直接对每个元素进行操作累乘至大于相邻的前一个元素时，可能最后会数据溢出，而且乘的2个数可能会很多，会时间超限。所以可以对每两个相邻的元素进行判断，判断他们之间差了2的多少次方。cnt记录的是当前元素和上个元素之间差的2的cnt次方。如：数组a为1, 4, 1, 4, 9，i = 2时，count = -2，cnt = max(0, 0 + -2)，i = 3时，count = 2，cnt = max(0, 0 + 2)，此时cnt表示a[3]和a[2]之间差了2的cnt次方，后续在cnt的基础上操作代表上个元素需要乘2的cnt次方，此时直接将当前元素和上个元素比较原元素的大小关系加上之前求出的cnt就可以得到当前元素需要乘2的cnt次方 ，i = 4时，count = -2，cnt = max(0, 2 + -2)，i = 5时，count = -2，cnt = max(0, 0 + -2)。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
ll a[N];
void solve() {
  ll n, res = 0;
  cin >> n;

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }

  ll cnt = 0, ans = 0;
  for (int i = 2; i <= n; i++) {
    ll start = a[i - 1], target = a[i], count = 0;
    // 计算当前元素与上一个元素之间的差值
    while (start < target)
      count--, start *= 2;
    while (start > target)
      count++, target *= 2;
	// 综合上个元素的乘2次数，计算当前元素乘2的次数
    cnt = max(0ll, count + cnt);
    res += cnt;
  }

  cout << res << endl;
}

int main() {
  int t;
  cin >> t;

  while (t--) {
    solve();
  }
  return 0;
}