给我们一个长度为n的序列a1,a2,a3,……,an,可以对序列执行以下操作任意次:
(1)任选序列中的一个元素ai(1≤i≤n), 对该元素执行除以2的操作,即用⌊ai/2⌋替换该元素的值。其中,⌊ ⌋为向下取整。
请问,将原序列转换为严格递增有序的序列最少需要执行上述操作多少次?
对于长度为n的序列而言,严格递增有序是指该序列必须满足:a1<a2<a3<……<an.
给我们一个长度为n的序列a1,a2,a3,……,an,可以对序列执行以下操作任意次:
(1)任选序列中的一个元素ai(1≤i≤n), 对该元素执行除以2的操作,即用⌊ai/2⌋替换该元素的值。其中,⌊ ⌋为向下取整。
请问,将原序列转换为严格递增有序的序列最少需要执行上述操作多少次?
对于长度为n的序列而言,严格递增有序是指该序列必须满足:a1<a2<a3<……<an.
第一行一个整数t(1≤t≤10000):测试用例数;
每个测试用例共2行:
第一行一个整数n(1≤n≤30):序列a的长度;
第二行共n个整数:a1,a2,a3,……,an的值(0≤ai≤2e9);
共t行,每个测试用例一行一个整数:将序列a转换为严格递增有序序列所需要的最少操作次数;
如果无法将序列转换为严格递增有序序列,请输出:-1。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
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次;