题意简述
ikrpprpp 发现了一个由整数组成的数组 $a$。
他喜欢公正，所以他希望将数组 $a$ 变得公平——也就是说，使其变为非递减数组。
为此，他可以在数组的某个索引 $1 \le i \le n$ 处执行一次“公正行为”，将 $a_i$ 替换为 $a_i ^ 2$（即将位置 $i$ 处的元素替换为它的平方）。
请问最少需要多少次公正行为才能使数组变为非递减数组？
思路分析
首先是最简单最直接的想法：暴力模拟。
如果 $ai \lt a{i-1}$，那么就进行若干次 $ai \gets a{i-1}^2$ 直至 $ai \ge a{i-1}$。
这样的缺点是显而易见的，即会轻易地爆掉 int ，甚至 long long。
那么如何缩小这个值域呢？
容易想到，如果为每一个 $a_i$ 都套上一个 $\log$，那么平方操作就变成了乘法操作。
更具体地，$\log_2 a_i^2 = 2 \log_2 a_i$。
但是还不够。long long 类型最多只够进行 63 次操作，这对于 $n \leq 2\cdot10^5$ 显然是不够用的。
既然如此，我们就可以再套一个 $\log$，把乘法操作变成加法操作。
即 $\log_2(\log_2 a_i^2)=\log_2(\log_2 a_i) + 1$。
考虑到浮点数的精度问题，我使用了二分来找每一个 $a_i$ 都需要加多少。
代码展示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<bits/stdc++.h>
using namespace std;
const int maxN = 3e5 + 10;
const double eps = 1e-7;
const double log2 = log(2);
int A[maxN];
double B[maxN];
inline void m_solve(){
int N;
scanf("%d",&N);
for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
for(int i = 2;i<=N;i++){
if(A[i] == 1 && A[i] < A[i-1]){
printf("-1\n");
return;
}
}
for(int i = 1;i<=N;i++) B[i] = log(log(A[i])/log2)/log2;
long long cnt = 0;
for(int i = 2;i<=N;i++){
if(A[i] == A[i-1]) continue;
long long l = 0;
long long r = 20000000000;
long long ans = 0;
while(l <= r){
long long mid = (l + r) >> 1;
if(B[i] + mid > B[i-1] || fabs(B[i]-B[i-1]+mid) < eps){
r = mid - 1;
ans = mid;
}else l = mid + 1;
}
cnt += ans;
if(ans != 0) A[i] = -1;
B[i] += ans;
}
printf("%lld\n",cnt);
}
int main(){
int T;
scanf("%d",&T);
while(T--) m_solve();
return 0;
}
|