问题 5879 --递增序列

5879: 递增序列★★

时间限制: 2 Sec  内存限制: 256 MB
提交: 67  解决: 40
[提交][状态][命题人:]

题目描述

给我们一个长度为n的序列a1,a2,a3,……,an,可以对序列执行以下操作任意次:

1)任选序列中的一个元素ai(1≤i≤n), 对该元素执行除以2的操作,即用⌊ai/2⌋替换该元素的值。其中,⌊ ⌋为向下取整。

请问,将原序列转换为严格递增有序的序列最少需要执行上述操作多少次?

对于长度为n的序列而言,严格递增有序是指该序列必须满足:a1<a2<a3<……<an.

输入

        第一行一个整数t(1≤t≤10000):测试用例数;

        每个测试用例共2行:

        第一行一个整数n1≤n≤30):序列a的长度;

        第二行共n个整数:a1,a2,a3,……,an的值(0≤ai≤2e9);

输出

        共t行,每个测试用例一行一个整数:将序列a转换为严格递增有序序列所需要的最少操作次数;

       如果无法将序列转换为严格递增有序序列,请输出:-1
样例输入
Copy
7
3
3 6 5
4
5 3 2 1
5
1 2 3 4 5
1
1000000000
4
2 8 7 5
5
8 26 5 21 10
2
5 14
样例输出
Copy
2
-1
0
0
4
11
0

提示

在第一个测试用例中,序列a为:[3, 6, 5],可以对a2执行一次操作:6/2=3; 再对a1执行一次操作:3/2=1;此时序列转换为:[1, 3, 5],严格递增有序,最少操作次数为2次。

在第二个测试用例中,无法将序列[5, 3, 2, 1]转换为递增有序序列,输出-1

在第三个测试用例中,序列[1, 2, 3, 4, 5]已经严格递增有序,输出0

在第四个测试用例中,序列的长度为1,已经严格递增有序,输出0

      在第五个测试用例中,序列a[2, 8, 7, 5],可以先对a3执行一次操作:7/2=3; 再对a2执行2次操作:8/2/2=2; 最后对a1执行一次操作:2/2=1;此时序列为:[1, 2, 3, 5],严格递增有序,所以最少操作次数为4次;

来源

 

[提交][状态]