P12836 [蓝桥杯 2025 国 B] 翻倍

题目描述

给定 $n$ 个正整数 $A_1, A_2, \ldots, A_n$,每次操作可以选择任意一个数翻倍。 请输出让序列单调不下降,也就是每个数都不小于上一个数,最少需要操作多少次?

输入格式

输入的第一行包含一个正整数 $n$。 第二行包含 $n$ 个正整数 $A_1, A_2, \ldots, A_n$。

输出格式

输出一个整数表示需要的最小操作次数。

说明/提示

**【样例说明】** 可以将序列变为: $4, 6, 8, 8, 14, 18$,总计需要 $0 + 1 + 2 + 3 + 1 + 1 = 8$ 次操作。 **【评测用例规模与约定】** 对于 20% 的评测用例,$n \leq 10, A_i \leq 100$。 对于 50% 的评测用例,$n \leq 5000, A_i < 2^{32}$,保证存在操作可以在所有 $A_i$ 小于 $2^{32}$ 的情况下满足题目要求。 对于 100% 的评测用例,$1 \leq n \leq 2 \times 10^5, 1 \leq A_i < 2^{32}$。