CSU-: sequence

Description

给出一个长度为N的正整数序列a，你有两种变换操作：

1.把数列中的某个数乘 2。

2.把数列中的所有数减 1。

现在你需要通过最少的变换操作把这个数列中的数全部变成 0。

Input

第一行一个N。下面 N 行，每行一个正整数 $ A_i $ 描述这个数列。1 <= n <=200000, 1 <= \(a _i\) <=\(10^9\)

Output

输出一行一个正整数，表示最少的变换次数。

Sample Input

212

Sample Output

3

---

题解

我们考虑一个例子\(a_1 = 2, a_2 = 1025\),需要多少次变换

首先假如\(a_1\)只变幻到1023那么a1和a2无法同时到0，那么\(a_1\)至少需要10次乘法变化，那么这10次什么时候乘呢，我们并不关心，但可以知道的是必然能够通过10次变换使\(a_1和a_2\)某一时刻相等，可以这么想，\(a_1\)先乘10次2变成2048然后可以减1可以减2...这样必然可以使\(a_1和a_2\)相等。

这样我们可以得出一个数要经过的乘法变化次数为它乘多少次2可以大于最大的数，把乘法和加法次数加起来即可

#include
    
     #define maxn 200050using namespace std;inline int getnum() {    int ans = 0; char c; int flag = 1;    while (!isdigit(c = getchar()) && c != '-');    if (c == '-') flag = -1; else ans = c - '0';    while (isdigit(c = getchar())) ans = ans * 10 + c - '0';    return ans * flag;}long long a[maxn];long long fast_pow(int a, int b) {    long long ans = 1;    while (b) {        if (b & 1) ans *= a;        a *= a;        b >>= 1;    }    return ans;}int main() {    int n = getnum();    long long maxx = 0;    for (int i = 1; i <= n; i++) {        a[i] = getnum();        maxx = max(a[i], maxx);    }    long long ans = 0;    for (int i = 1; i <= n; i++) {        int tmp = int(log2(maxx / a[i]));        if (a[i] * fast_pow(2, tmp) < maxx) tmp++;        ans += tmp;    }    printf("%lld", ans + maxx);    return 0;}