问题 A:序列
文件提交:无需freopen
内存限制:128 MB
时间限制:1.000 S
评测方式:普通裁判
命题人:
提交:2
解决:2
题目描述
法普塔见到失忆的雷古后难以置信,决定问他一个简单的问题来检测他的智力:
给你一个长度为 $N$ 的序列 $a$。你可以对这个序列进行操作:
选择一个正整数 $i(1\le i \le N)$,设 $x=\max_{1\le j \le N}a_j$,然后令 $a_i=\lfloor \dfrac{a_i}{x}\rfloor$(表示计算结果向下取整)。
求最少操作几次可以使所有 $a_i=1$,如果无解输出 $-1$。
给你一个长度为 $N$ 的序列 $a$。你可以对这个序列进行操作:
选择一个正整数 $i(1\le i \le N)$,设 $x=\max_{1\le j \le N}a_j$,然后令 $a_i=\lfloor \dfrac{a_i}{x}\rfloor$(表示计算结果向下取整)。
求最少操作几次可以使所有 $a_i=1$,如果无解输出 $-1$。
输入
第一行一个正整数为 $N$。
第二行 $N$ 个整数,表示 $a_1,a_2,a_3,\cdots,a_n$。相邻两数中间用一个空格分开。
$1\le N\le 2\times 10^5,0\le a_i\le 2^{31}-1$
输出
一行一个整数,表示答案。
样例输入-1 复制
5
1 2 3 4 5
样例输出-1 复制
4
样例输入-2 复制
2
0 123
样例输出-2 复制
-1
提示
样例解释1:
第一步:最大值 $x=5$, 选择 $a_5/x=5/5=1$
第二步:最大值 $x=4$, 选择 $a_4/x=4/4=1$
第三步:最大值 $x=3$, 选择 $a_3/x=3/3=1$
第四步:最大值 $x=2$, 选择 $a_2/x=2/2=1$
最后所有数都变为 $1$,找不到更少的操作次数的方案了