题目描述
难度分:$1700$
输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。
每组数据输入$n(1 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。
每次操作,你可以把一个$a[i]$变成$a[i] \times 2$。你需要使数组$a$非递减,也就是$a[i] \leq a[i+1]$。输出最少操作次数。
输入样例
9
1
1
2
2 1
3
3 2 1
4
7 1 5 3
5
11 2 15 7 10
6
1 8 2 16 8 16
2
624323799 708290323
12
2 1 1 3 3 11 12 22 45 777 777 1500
12
12 11 10 9 8 7 6 5 4 3 2 1
输出样例
0
1
3
6
10
3
0
2
66
算法
贪心
贪心的策略很容易想到,从前往后贪,如果发现$a[i-1] \gt a[i]$,说明$a[i]$是需要倍增的。但遗憾的是,$a[i]$可能倍增的次数非常多,导致$long$ $long$也存不下,而且$python$的大数计算效率也堪忧,所以没办法偷鸡,只能想办法优化。
这里开辟一个$cnt$数组,$cnt[i]$表示$a[i]$倍增的次数。当比较$a[i-1]$和$a[i]$两个元素的大小关系时,要综合考虑$(a[i-1],cnt[i-1])$和$(a[i],cnt[i])$。比较的时候分为以下三种情况:
- $cnt[i-1] \gt cnt[i]$,让$a[i-1]$倍增$cnt[i-1]-cnt[i]$次,中间只要$\gt a[i]$马上返回,由于遍历到$a[i]$时$cnt[i]=0$,所以受到$a[i] \leq 10^9$的限制,乘不了多少次就会返回
false
(返回true
表示满足$a[i-1] \leq a[i]$)。如果没返回false
,而是最后返回了true
,也说明乘的次数不多,不影响效率。 - $cnt[i-1] \lt cnt[i]$,让$a[i]$倍增$cnt[i]-cnt[i-1]$次,中间只要$\geq a[i-1]$马上返回
true
,否则最后返回false
。 - $cnt[i-1]=cnt[i]$,直接比较$a[i-1]$和$a[i]$。
如果比较$a[i-1]$和$a[i]$发现不满足单调不减,也需要分为以下两种情况来计算贡献:
- $cnt[i-1] \leq cnt[i]$,此时有$a[i-1] \gt a[i] \times 2^{cnt[i]-cnt[i-1]}$,让$a[i]$在先倍增$cnt[i]-cnt[i-1]$次的基础上,看还需要倍增多少次可以超过$a[i-1]$,由于受到值域限制,这个过程会很快。
- $cnt[i-1] \gt cnt[i]$,此时有$a[i-1] \times 2^{cnt[i-1]-cnt[i]} \gt a[i]$,假设$a[i-1]$最多倍增$t_1$次可以保证$a[i-1] \leq a[i]$成立,可以模拟求得$t_1$,而此时已经倍增了$cnt[i-1]-cnt[i]$次,所以多倍增了$cnt[i-1]-cnt[i]-t_1$次,$a[i]$也需要倍增相同的次数。但是也有可能原数组中满足$a[i] \lt a[i-1]$,所以还需要计算一下原始的$a[i]$倍增多少次可以超过原始的$a[i-1]$。假设为$t_2$次,那这种情况下对答案的贡献就是$cnt[i-1]-cnt[i]-t_1+t_2$。
复杂度分析
时间复杂度
遍历数组$a$的时间复杂度是$O(n)$,而对于每个$a[i]$,需要进行一系列的倍增操作,因受到值域$[1,10^9]$的限制,这个倍增操作大概就是几十次。因此,算法整体的时间复杂度为$O(nlog_2A)$,其中$A$就是值域的最大范围。
空间复杂度
除了输入的原数组$a$,还开辟了一个$cnt$数组,用于存储每个$a[i]$乘以$2$的次数。因此,算法整体的额外空间复杂度为$O(n)$。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
int T, n, cnt[N];
LL a[N];
bool cmp(int i) {
int cnt1 = cnt[i - 1], cnt2 = cnt[i]; // a[i-1]和a[i]分别乘了几次2
int delta = abs(cnt1 - cnt2);
if(cnt1 > cnt2) {
LL res = a[i - 1];
while(delta--) {
res <<= 1;
if(res > a[i]) return false;
}
return true;
}else if(cnt1 < cnt2) {
LL res = a[i];
while(delta--) {
res <<= 1;
if(res >= a[i - 1]) return true;
}
return false;
}else {
return a[i - 1] <= a[i];
}
}
LL solve() {
if(n == 1) return 0;
LL ans = 0;
for(int i = 2; i <= n; i++) {
if(!cmp(i)) {
// a[i-1]>a[i]
int x = cnt[i - 1], y = cnt[i];
if(x <= y) {
LL num = a[i];
for(int j = 0; j < y - x; j++) {
num *= 2;
}
int t = 0;
while(num < a[i - 1]) {
num *= 2;
cnt[i]++, t++;
}
ans += t;
}else {
LL num = a[i - 1];
int t1 = 0;
while(num*2 <= a[i]) {
num *= 2;
t1++;
}
num = a[i];
int t2 = 0;
while(num < a[i - 1]) {
num *= 2;
t2++;
}
cnt[i] += x - y - t1 + t2;
ans += x - y - t1 + t2;
}
}
}
return ans;
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
cnt[i] = 0;
}
printf("%lld\n", solve());
}
return 0;
}