题目
A. Dense Array
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Polycarp 调用数组密集，如果任意两个相邻元素中的较大者不超过较小元素的两倍。更正式地说，对于任何i我 (1≤i≤n?11≤i≤n?1），必须满足此条件：
max(a[i],a[i+1])min(a[i],a[i+1])≤2max（a[i]，a[i+1]）min（a[i]，a[i+1]）≤2
例如，数组[1,2,3,4,3],[1,1,1]和[5,10]是密集的。和阵列[5,11],[1,4,2],[6,6,1]是not dense.
You are given an array a of n整数。需要添加到数组中以使其密集的最小数字数是多少？您可以在数组中的任意位置插入数字。如果数组已经密集，则无需添加任何数字。
例如，如果a=[4,2,10,1]，那么答案是5，而数组本身在将元素插入其中后可能如下所示：a=[4,2,3_,5_,10,6_,4_,2_,1]（还有其他方法可以构建这样的a).
Input
第一行包含一个整数t (1≤t≤1000).然后t测试用例如下。
每个测试用例的第一行包含一个整数n (2≤n≤50） — 数组的长度a.
下一行包含n整数a1,a2,…,an (1≤ai≤50).
Output
For each test case, output one integer — the minimum number of numbers that must be added to the array to make it dense.
Example
input
Copy
6 4 4 2 10 1 2 1 3 2 6 1 3 1 4 2 5 1 2 3 4 3 12 4 31 25 50 30 20 34 46 42 16 15 16
output
Copy
5 1 2 1 0 3
Note
The first test case is explained in the statements.
在第二个测试用例中，您可以插入一个元素，a=[1,2_,3].
在第三个测试用例中，您可以插入两个元素，a=[6,4_,2_,1].
在第四个测试用例中，您可以插入一个元素，a=[1,2_,4,2].
在第五个测试用例中，数组a已经很密集了。
代码
/*题目大意
列表中插入数字，使向邻数字满足大/小<=2,求最小插入数字个数*/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;int main()
{int t,n;cin >> t;while(t--){int i,sum=0,a[55]={0},s,x;cin >> n;for(i=0;i<n;i++){cin >> a[i];}for(i=0;i<n-1;i++){s=max(a[i],a[i+1]);x=min(a[i],a[i+1]);while(s>2*x)//当相邻两项的大/小<=2符合条件时停止{sum++;x*=2;//小*2可用来填补大与小直接的数，因为求最小插入数，所以 * 大/小的最大比值}}cout << sum <<endl;}return 0;
}